В 525 г. войско Елевзоя на нескольких десятках кораблей вышло из Габазы, гавани Адулиса, и высадилось на красноморском побережье Йемена, по-видимому, близ порта Мухван (ныне Моха). Елевзой разгромил войско химьяритского царя, который был взят в плен и казнён (согласно распространенному арабо-мусульманскому преданию о зу Нувасе, он покончил с собой в ходе сражения). Эфиопская агиографическая традиция сообщает, что во время решающей битвы аксумские воины видели, как на их стороне сражается св. Пантелеимон. После победы на трон Химьяра был возведён христианин из местной знати Сумйафа Ашва (у Прокопия – Есимифей), а во главе клира встал епископ Григентий. В 526 г. (вероятно, весной) Елевзой покинул Южную Аравию, а около 534 – 535 гг. власть над Химьяром захватил аксумский военачальник Абраха; попытки Елевзоя подчинить мятежника не увенчались успехом. У Иоанна Малалы содержится повествование о походе на Химьяр в 529 г. аксумского царя Анды, вызванном торговой конкуренцией с Аравией. Одержав победу, Анда по обету принял христианство и отправил в Александрию посольство с просьбой прислать епископа, крестить его народ и принять их в византийское подданство. Вслед за Иоанном Малалой этот рассказ повторяют Иоанн Эфесский и Феофан Исповедник, называя царя соответственно Айдогом (в Хронике Зукнина – Индуг) и Ададом. Хронология события заставляет исследователей отнести повествование ко времени правления Елевзоя, но при нём Эфиопия уже была христианизирована. Поскольку у Иоанна Эфесского и Феофана Исповедника наряду с этим имеются исторически верные сообщения об экспедиции Елевзоя в отмщение за Награнских мучеников, исследователями было высказано предположение, что Иоанн Малала перепутал поход Елевзоя с аналогичным походом на химьяритов его деда, царя Элла Амиды. Однако ни этот поход, ни существование Элла Амиды не находят подтверждения в достоверных источниках (в первую очередь, эпиграфических), и фигура царя Анды представляется исследователям легендарной. В соответствии с агиографической традицией после возвращения в Эфиопию аксумский царь оставил престол, принял монашество, уединился в келье и не покидал её до самой кончины, последовавшей, согласно православному преданию, через 15 лет после пострига. Свой царский венец Елевзой отослал в Иерусалим и просил патриарха повесить его над входом в Гроб Господень. Однако другие источники не подтверждают отречения Елевзоя, по крайней мере, в течение нескольких лет после похода. Согласно Прокопию Кесарийскому, император Юстиниан I (527–565 гг.) отправил к Елевзою и Есимифею посла Юлиана с просьбой о поддержке в войне против Персии, а также о закупке шёлка в Индии и его последующей продаже византийцам, чтобы им не приходилось приобретать его у персов. Это посольство датируется периодом между 525 и 531 гг. Оба царя обещали выполнить пожелание императора, но не смогли, поскольку торговля шёлком через Индию была монополизирована Персией. Впоследствии к аксумитам было отправлено другое византийское посольство, во главе с Нонном, который оставил сведения о своей миссии в сочинении «История», сохранившемся в составе «Библиотеки» Константинопольского патриарха Фотия (IX в.). Ещё до химьяритской кампании 518–519 гг. Елевзой совершил победоносный поход внутри Эфиопии против племён, названных в сабеографичных надписях «агуэзат», что исследователи отождествляют с геэзами, давшими название классическому эфиопскому языку. По мнению исследователей, именно на это событие указывает эфиопское синаксарное Житие Елевзоя, повествуя о том, как «он прошёл скрытно от страны Аксума до земли Матары (селение в Эритрее с древним городищем) и уничтожил мятежников», которых автор Жития называет «народом Гоморры».