Проблема была не только в конфликтах между военачальниками, но и в том, что они стремительно теряли поддержку халкидонян, населявших Италию. Велизарий умел налаживать отношения с местными жителями и хорошо платил им за продовольствие для византийского войска. В конце концов, он ведь был очень богат и содержал часть византийской армии за свой счет. Его преемники не имели подобных нравственных установок, не отличались состоятельностью и видели в военной кампании возможность обогатиться. Но не только армия начала бесстыдно грабить местное население. Поскольку теперь Равенна принадлежала ему, Юстиниан решил, что Италия, как одна из провинций империи, должна платить в казну. Он послал туда одного из самых эффективных сборщиков налогов, логофета Александра, прозванного «ножницами» за то, что он якобы мог обрезать края золотых монет, не портя их окружность. Он ввел новые налоги и в то же время стал сокращать расходы, в частности выплаты солдатам. Таким образом ему удалось одновременно оттолкнуть от Византии местное население и подорвать боевой дух армии.
Последствия этого не были бы столь серьезны, останься остготы разобщенными и без верховного правления. Витигеса Велизарий пленил в Равенне в 540 году и увез в Константинополь. Когда стало ясно, что византийский военачальник не собирается объявлять себя императором Западной Римской империи, остготы избрали своим королем правителя Вероны Ильдебада. Тот был храбрым полководцем, но неразумными поступками навлек на себя гнев некоторых из своих подданных. Однажды вечером на пиру, когда сидевший за столом Ильдебад наклонился вперед, чтобы взять еще еды, один из его охранников подошел к нему сзади и отрубил ему голову, оставив обезглавленный труп сидеть с куском в руке. После этого королем был провозглашен Эрарих, но буквально через несколько месяцев он разделил участь прежнего правителя. На престоле его сменил племянник Ильдебада Тотила.
В отличие от своих недолго правивших предшественников, новый король остготов проявил себя как блестящий полководец. Вскоре после того, как летом 542 года византийцы не сумели взять Верону, Тотила сошелся с ними в открытом бою у города Фаэнца. Проявив хитрость, он послал 300 всадников напасть на противника с тыла в самый разгар сражения, и в результате византийцы впали в панику и обратились в бегство, подумав, что им угрожает куда более многочисленное войско. После этого византийские полководцы заперлись за стенами Равенны, а Тотила двинулся через всю Италию, беря город за городом. В 543 году ему покорился Неаполь, в 546-м – Рим, а за ним и то немногое, что осталось у византийцев в Италии, кроме Равенны. Успех Тотилы отчасти объяснялся тем, что он действовал в интересах местного населения. Византийцы несли с собой халкидонскую веру, но они были в Италии чужеземцами. А у герулов, персов и мавров, составлявших большую часть византийской армии, общего с жителями Италии было и того меньше, и Тотила в полной мере воспользовался в пропагандистских целях безжалостными поборами логофета Александра. У тех итальянцев, которые оставались под властью Византии, жизнь была почти невыносимой. Риму, прежде чем он сдался Тотиле, пришлось выдержать несколько лет осады, в течение которых жители фактически голодали. Некоторые кончали с собой, бросаясь в Тибр. И будто мало было несчастий в Италии, завоевание Северной Африки, которое вроде бы произошло легко и быстро, оказалось не таким полным и безоговорочным. Хотя вандалы были разгромлены, берберские племена остались непокоренными. В 544 году они подняли мятеж, в ходе которого погиб византийский полководец Соломон, заняли большую часть провинции и заставили византийцев укрыться в их крепостях.