Однако эти великолепные достижения дорого обошлись императору. Трибониан и Иоанн стали одними из самых ненавидимых людей в империи, и тот факт, что Трибониан был известным корыстолюбцем, да к тому же варваром, положения не облегчал. Если бы император прислушался к тому, что говорит народ, он бы услышал предвещающий беду ропот несогласия. Раненое самолюбие влиятельной знати требовало отмщения, а простые люди, страдающие от тяжелых поборов, стали задаваться вопросом: не станет ли жизнь намного проще, если трон займет другой человек?
Юстиниан был слишком занят внешней политикой, чтобы заметить сгущающиеся тучи на домашнем горизонте. В 528 году наконец разразилась война с Персией, и он полностью ушел в реорганизацию восточной армии. Стареющий персидский царь выслал огромное войско, чтобы разгромить римлян — но Велизарий разбил его, очередной раз продемонстрировав свои таланты, а вдобавок смог захватить часть персидской Армении. Это была первая очевидная победа в противоборстве с Персией на памяти живущих, и прозвучала она как призыв к возрождению империи.
Эта победа также имела следствием падение царя вандалов в Африке. Годами он с все большим трудом сохранял равновесие, но недавнее торжество византийской армии сделало его позицию почти несостоятельной. С одной стороны, ему приходилось задабривать Юстиниана, чтобы держать войска империи подальше, но слишком много усилий, направленных на ублажение Византии, неизбежно вызывали обвинения в предательстве со стороны собственных подданных. Большинство вандалов опасались за свою независимость и хотели, чтобы их правитель занял жесткую позицию, но царь выбрал именно этот момент, чтобы выпустить новую серию монет с ликом императора. Эта несвоевременная попытка снискать расположение восточного двора стоила ему трона. При поддержке разъяренной вандальской знати кузен короля Гелимер сверг его и занял трон Карфагена.
С самого начала Гелимер дал понять, что не позволит Константинополю запугать себя. Когда Юстиниан прислал письмо с протестом против незаконного захвата власти, Гелимер велел ему не вмешиваться в чужие дела и изящно напомнил, что последний византийский поход против его королевства завершился полным провалом. Если византийцам так не терпится получить обратно их земли, заявил он, пусть придут и возьмут их. Мечи вандалов всегда готовы к встрече.
Юстиниан был несколько разочарован сменой вандальских королей, поскольку был абсолютно уверен, что при правильном дипломатическом нажиме возможно вернуть Северную Африку в римскую сферу влияния, не потеряв ни одного солдата. Но воинственная позиция Гелимера тоже вполне подходила для этого. Это высокомерное письмо явилось оскорблением, на которое следовало ответить — тем самым оно весьма помогло имперской пропаганде и обеспечило превосходный предлог для вторжения. Вандальские захватчики слишком долго грабили римскую землю и пренебрежительно относились к Константинополю. Теперь они должны узнать, что бывает, если дразнить римскую волчицу.
