В дальнейшем, однако, выяснилось, что контроль империи над завоеванными территориями на Западе был еще весьма слаб, и враги возобновили военные действия.
В Африке, после того как она была отвоевана от вандалов, происходили периодические войны с соседними мавританскими племенами до тех пор, пока постепенно они не были к концу правления Юстиниана приведены в полную покорность силой оружия и дипломатии. Главным же злом оказались там солдатские мятежи, подогреваемые хронически нерегулярной выплатой жалованья и амбициями остатков вандальского населения. Вандалы, так же как и некоторые из воинов императора, были арианами и еще не полностью утратили родную речь и обычаи под натиском латинского языка и римской культуры. Это создавало опасную обстановку, когда переход воинов из лагеря императора в лагерь мятежников и обратно был чрезвычайно легок. Сначала весной 536 г. вспыхнул бунт в частях армии, размещенных в Карфагене. Под руководством Стотцы, бывшего букцеллярием римского полководца Мартина, мятежники собрали войско в 8000 воинов из бывших солдат, вандалов, беглых рабов и колонов. Они расположились недалеко от Карфагена, в который к тому времени прибыл сам Велизарий с сотней букцелляриев для спасения положения. В 60 км от Карфагена около города Мамбресы Стотца был наголову разбит: в начале битвы при сильном противном ветре он стал перестраивать свое войско и не выдержал фронтального удара. Вскоре, однако, Стотца снова собрал под своим знаменем недовольных и смог дать новую битву около города Скалэ-Ветерес выступившему против него римскому войску под командованием Германа, кузена императора Юстиниана (см. Приложение). В ней он и был окончательно разбит и с оставшимися сторонниками ушел к маврам. Однако спустя несколько лет созрел новый мятеж: в 545 г. вакантный магистр и по совместительству дукс Нумидии Гонтарис составил заговор для узурпации власти в Африке. Он вошел в сношения с враждебными империи маврами, и ему удалось даже захватить Карфаген. К нему тут же присоединились бывшие соратники уже погибшего к тому времени Стотцы: 500 римских дезертиров, 80 дезертиров-гуннов и 400 непокорившихся вандалов. Впрочем, через месяц после переворота узурпатор был убит в результате контрзаговора, организованного тагматархом Артабаном, и законность была восстановлена.
Тем временем готы, оставшиеся в Италии, воспользовались алчностью имперских властей, настроивших поборами население Италии против Константинополя. К тому же их действиям способствовало то, что войска империи были распылены по гарнизонам, и в них совершенно упала дисциплина. Готы собрались с силами на севере Италии, избрали себе в 540 г. нового короля по имени Ильдибад, который смог, опираясь всего лишь на какую-то тысячу воинов, собрать уже достаточно крупное войско и одержать победу над двинувшимся против него войском. В мае 541 г. он, однако, был убит на пиру одним из своих телохранителей, и королем был избран Эрарих. Эрариха, пытавшегося договориться с императором, постигла та же участь, и осенью 541 г. королем стал племянник Ильдибада — Тотила. Собрав до 5000 воинов, готы нанесли поражение имперским отрядам у Вероны, Фавенции и у Муцелла около Флоренции (июнь 542 г.) и постепенно стали теснить врага, несмотря на его численное преимущество. Воспользовавшись нерешительностью имперского войска, Тотила разгромил римлян, захватив все знамена. Несогласованные действия римских командиров не смогли остановить готскую реконкисту, и вскоре почти весь Апеннинский полуостров, за исключением крупных городов в Средней Италии и на крайнем Юге, оказался снова во власти готов. Продуманная политика Тотилы привела к тому, что к нему массами стали переходить уставшие от тягостей войны и налоговых поборов местные жители, давно не получавшие жалованья солдаты-дезертиры и беглые рабы. Война свелась к серии отдельных столкновений небольших отрядов и к продолжительным осадам городов. Рим на протяжении последнего периода войны осаждали пять раз, и несколько раз он переходил из рук в руки, что все вместе привело его на какой-то период к полному обезлюдению и к гибели большинства его жителей и многих зданий. Сельское население, обираемое обеими сторонами, терпело ужасные лишения. На короткий период (осень 544— весна 546 и осень 547—осень 548) в Италию снова прибыл Велизарий с небольшими подкреплениями, но дела зашли уже слишком далеко, и без серьезных свежих сил делать там было нечего. Император же не обращал на дела в Италии должного внимания, посылая лишь небольшие силы. После того как Тотила взял Рим 17 декабря 546 г., готы контролировали уже всю Италию, кроме Равенны, Анконы и нескольких городов на крайнем Юге (Гидрунт, Кротон). Некоторое время войска империи удерживали еще устье Тибра и даже вновь заняли сам Рим, полностью покинутый населением, но были вскоре (16 января 550 г.) выбиты и оттуда. На сей раз Тотила восстановил Вечный Город и сделал его своей столицей. Готы построили флот, перенесли военные действия на море и даже стали угрожать побережью Балкан. Стратегия Юстиниана — действовать небольшими отрядами и планомерно бороться за каждый небольшой городок — не оправдала себя. Нужна была крупная армия с талантливым полководцем, который смог бы переломить ход войны в нескольких генеральных сражениях.