Вероятно, к этому времени относятся царские гробницы Аксума. В их подземных помещениях встречается знак креста, однако на скромном месте. Возможно, он свидетельствует о христианской вере строителей, а не погребенных[187].
Характерно, что в этот период аксумские монеты украшались знаком креста. «Этническое прозвище» на них заменено «демагогической формулой». Судя по монетам, в конце IV — начале VI в. правили следующие аксумские цари: Вазеба II, МНDYS[188], Эон, Эсбаэль, Тезена, Калеб, Незана и (или) Незона. Из них Калеб, или Элла-Асбеха, царствовал в 20–30-х годах VI в., а Тезена был его отцом. На монетах Элла-Асбеха именуется Калебом (или Халебом), сыном Тезены ('υιος Θεζιενα или Θεζενα). Однако, согласно версии «С» «Списков царей», непосредственным предшественником Калеба на аксумском престоле был Элла-Ахйава[189]. «Спискам царей» известны также Калеб и Тезена[190].
Несмотря на продолжающийся расцвет Аксума, его политика терпит ряд неудач. В странах, находящихся в сфере аксумского влияния, — Южной Аравии, Северной Нубии и Беджа — образуются сильные государственные объединения блеммиев, нуба и хымьяритов. В V в. блеммии-беджа и нуба усиливают натиск на римско-византийский Египет, опустошают и даже захватывают пограничные территории — часть Северной Нубии и район Алебастровых гор. Особенно разрушительными были набеги 429 и 450 гг. Во главе блеммиев стоит царь (тиран), который, по свидетельству Олимпиодора, назначал «архонтов» над отдельными племенами. Неизвестно, подчинялся ли он хотя бы формально аксумскому царю; во всяком случае, византийцы сносились с блеммиями без посредства Аксума. В отличие от аксумитов блеммии твердо придерживаются языческих культов, в частности Исиды, и не принимают христианства. Нуба также имели своих царей, независимых от Аксума; так далеко на северо-запад аксумское влияние уже не доходило. Зато они находились под политическим влиянием Византии.
В Южной Аравии господство окончательно переходит к хымьяритам; в конце IV–V в. хымьяриты владели всей Южной и частично Центральной Аравией. Аксумские цари по-прежнему претендовали на гегемонию в Южной Аравии; по-видимому, некоторые хымьяритские цари признавали их власть. Так, царя Ма'дикариба («Маадкарима»), правившего в начале VI в., сирийская традиция считает христианином и ставленником Эфиопии. Характерное утверждение содержится в том варианте «Послания» Симеона Бетаршамского, который приводит Иоанн Эфесский. По его словам, хымьяритский царь-иудей Зу-Нувас якобы писал лахмидскому царю аль-Мунзиру III: «Да будет тебе известно, что умер царь, которого поставили кушиты (аксумиты) в нашей земле; пришло зимнее время, и не смогли кушиты прийти в нашу землю и поставить царя-христианина, как обычно»