Сразу вслед за тем началась Итальянская война. Летом 535 года две небольшие, но хорошо обученные и оснащённые армии вторглись в пределы Остготской державы: Мунд захватил Далмацию, а Велисарий — Сицилию. С запада Италии грозили подкупленные римским золотом франки. Устрашённый король готов Теодат начал было переговоры о мире и соглашался уже отречься от престола, но в конце года Мунд погиб в стычке, а Велисарий спешно отплыл в Африку на подавление солдатского мятежа. Теодат, осмелев, прервал переговоры и заключил под стражу императорского посла.
Мятеж в Африке был вызван решением Юстиниана присоединить все земли вандалов к фиску, между тем как солдаты надеялись, что император разделит их между ними. Легионы восстали, провозгласив командующим простого солдата Стоцу. Почти вся армия поддержала его, и Стоца осадил Карфаген, где заперлись немногочисленные верные императору войска. С прибытием Велисария мятежники отступили от города, но война на этом не утихла. Собрав под свои знамёна рабов и уцелевших вандалов, Стоца ещё десять лет боролся против императорских войск. Окончательно страна была покорена только к 548 году. К этому времени, по словам Прокопия, Африка оказалась до такой степени разорённой, что встретить там человека на протяжении долгого пути, было делом нелёгким и даже примечательным. А между тем до войны в этой богатейшей провинции одних вандалов проживало около восьми миллионов человек, не считая потомков тех, кто прибыл сюда во времена римского владычества. Вина за этот ужасающий разгром целиком лежала на императоре, который, не позаботившись о прочном обеспечении своей власти, спешно отозвал из Африки Велисария, совершенно безосновательно возведя на него обвинения в тирании. После этого он немедленно послал оценщиков земли и наложил прежде небывалые и жесточайшие налоги. Земли, что получше, он присвоил себе, стал преследовать ариан, а солдатам перестал платить жалованье. Возникший вследствие этих причин мятеж и привёл к конечному разорению страны.
Одновременно с Африканской войной продолжалось завоевание Италии. Зимой 536 года Велисарий вернулся на Сицилию. В середине ноября римляне штурмом взяли Неаполь. Готский король Теодат был убит заговорщиками, а престол захватил Витигас. Но эта перемена уже не могла спасти готов. В ночь с 9 на 10 декабря 536 года Велисарий вступил в Рим. Попытка Витигаса отбить город, несмотря на более чем десятикратное превосходство в силах, оказалась неудачной. В конце 539 года Велисарий осадил Равенну, а следующей весной столица готов пала. Они предложили Велисарию быть их королём, но полководец отказался. Тем не менее подозрительный Юстиниан отозвал Велисария из Италии и отправил сражаться с персами, которые в 540 году внезапно напали на восточные провинции Византии. Следующие десять лет, когда империи пришлось одновременно вести три тяжёлые войны, были самыми трудными в царствование Юстиниана.
