Отношения Византии с вандалами складывались по-разному. Своей первейшей обязанностью император Константинополя счел освобождение принадлежавших к правящему дому дам, которые были пленены в Риме в 455 году и вывезены в Африку. Своей цели он добился лишь в 462 году, когда императрица Евдоксия и ее дочь Плацидия смогли вернуться в восточную столицу, однако второй ее дочери, Евдокии, пришлось остаться при дворе вандалов, поскольку к тому времени она уже была женой королевского сына, принца Гунериха.
Но независимо от дипломатических попыток и всяческих иных соглашений Лев, будучи представителем интересов империи, не имел права отказываться от Африки, которая была исключительно важна как основная житница Италии. Впрочем, вандалы тоже не стремились к прочному миру и время от времени нападали даже на греческое побережье.
Лев готовился к войне старательно, не жалея денег на приготовления. Его казна была в неплохом состоянии, поскольку уже не было необходимости платить дань гуннам, но все равно страна в течение еще нескольких лет ощущала на себе тяжесть этого усиленного вооружения.
В 468 году корпус под командованием Ираклия двинулся в поход из Египта и быстро занял Триполитанию — то есть нынешнее побережье Ливии. Одновременно были начаты военные действия на западе. Войска Антемия под командованием Марцеллина вытеснили вандалов с Сардинии, а мощный византийский военный флот, командовал которым зять Льва Василиск, разбил эскадры вандалов и встал на якорь вблизи от Карфагена.
Казалось, что судьба Гензериха уже решена. Поэтому Василиск, уверенный в своей победе и в своем подавляющем преимуществе, согласился на пятидневное перемирие. Король вандалов воспользовался этой передышкой для подготовки предательского удара. Благоприятное направление ветра позволило ему подвести пылающие корабли вплотную к вражескому флоту и разжечь пожар, уничтоживший большую часть судов противника. Так что весь поход закончился совершенно неожиданным позорным поражением.
Василиску удалось спастись, но в Константинополе ему пришлось искать убежища в храме Святой Софии — его повсеместно обвиняли в предательстве, хотя в сущности виной случившемуся была лишь его неопытность. В конце концов, благодаря заступничеству императрицы он все же был помилован. Но тем временем погиб действительно заслуженный полководец Западной империи, Марцеллин — его предательски убили на Сицилии.
В этой ситуации Лев вынужден был пойти на мир с вандалами. Они получили обратно Триполитанию и Сардинию, а впоследствии сумели занять еще и Сицилию.
Вся эта война — как ее начало, так и заключение позорного мира — была тесно связана с внутренними политическими интригами в Восточной империи. Речь идет прежде всего о действиях Аспара. Он изначально был ярым противником войны — и в общем-то, оказался прав, что и показал ход военных действий. Все дело было в том, что никто кроме него не оценил должным образом полководческих талантов Гензериха. Однако в глазах общественного мнения Аспар просто был сторонником германцев.
В 664 году Льву удалось ослабить положение Аспара. Помощь в этом оказал ему князь исавров — народа, заселившего южное побережье Малой Азии. Он прибыл в столицу с документами, якобы свидетельствовавшими о том, что сын Аспара Ардабур, командовавший войсками на восточной границе, вступил в предательский сговор с правителем Персии. Ардабур был отстранен от командования, зато князь получил должность начальника личной охраны императора, а вдобавок еще и руку его старшей дочери Ариадны, при этом он сменил свое родовое имя и стал зваться Зеноном — под этим именем он и вошел в историю.
Именно эти изменения в расстановке сил внутри страны позволили Льву подготовиться к войне против вандалов. Но с другой стороны, ее позорное окончание стало политическим триумфом Аспара.
В борьбе с Зеноном он не гнушался любыми средствами. Когда тот был занят изгнанием из Фракии орды гуннов, Аспар подослал к нему своих людей, и князь едва избежал смерти, а после этого покинул двор и принял командование стоявшими на востоке войсками.
В 470 году Лев под давлением Аспара возвел его сына Патрикия в ранг кесаря, как бы дав понять, что тот станет его преемником. Таким образом, диадема и императорский пурпур были уже практически в руках выходцев из Ирана. Но это назначение встретилось с активным противодействием ортодоксальных христиан столицы — Патрикий, как и его отец, был арианином. Аспар был вынужден поклясться в том, что в нужное время его сын примет господствующую религию. И наконец, старания Аспара были увенчаны женитьбой Патрикия на младшей дочери императора, Леонтии — теперь он был связан с правящим домом семейными узами.