Затем в феврале 537 г., готы огромным войском в несколько десятков тысяч человек осадили Рим, к обороне которого Велизарий хорошо подготовился. Многократные попытки взять город и сражения под стенами показали полное господство на поле боя римских конных лучников и превосходство полководческого таланта Велизария. Начиная с апреля 537 г. к Велизарию подходили подкрепления: 1600 нанятых конных гуннов, славян и антов под командованием магистров Мартина и Валериана, 300 всадников Зенона, 3000 исавров-пехотинцев Павла и Конона, 800 фракийских федератов Иоанна, племянника Виталиана, и 1000 всадников регулярной кавалерии Александра и Маркентия. Однако снять осаду не удавалось, и в городе начался голод. Постепенно Велизарий перенес войну в более северные области Италии, чем вынудил готов в марте 538 г. снять осаду с уже почти опустевшего Рима. В июне 538 г. прибыло еще подкрепление численностью около 7000 воинов (в т. ч. 2000 герулов) под командованием евнуха Нарзеса, но обилие полководцев привело к несогласованности действий. В результате имперские войска потерпели ряд поражений, и готами был взят и полностью разграблен один из крупнейших городов Средиземноморья— Медиолан (совр. Милан). Все взрослые мужчины (30 000) были перебиты, а женщины и дети уведены в рабство. Весной 539 г. командование снова было сосредоточено в руках Велизария, который постепенно сжал кольцо вокруг столицы Италии Равенны и пленил готского короля. Война фактически закончилась. Велизарий отбыл в Византий.
В дальнейшем, однако, выяснилось, что контроль империи над завоеванными территориями на Западе был еще весьма слаб, и враги возобновили военные действия.
В Африке, после того как она была отвоевана от вандалов, происходили периодические войны с соседними мавританскими племенами до тех пор, пока постепенно они не были к концу правления Юстиниана приведены в полную покорность силой оружия и дипломатии. Главным же злом оказались там солдатские мятежи, подогреваемые хронически нерегулярной выплатой жалованья и амбициями остатков вандальского населения. Вандалы, так же как и некоторые из воинов императора, были арианами и еще не полностью утратили родную речь и обычаи под натиском латинского языка и римской культуры. Это создавало опасную обстановку, когда переход воинов из лагеря императора в лагерь мятежников и обратно был чрезвычайно легок. Сначала весной 536 г. вспыхнул бунт в частях армии, размещенных в Карфагене. Под руководством Стотцы, бывшего букцеллярием римского полководца Мартина, мятежники собрали войско в 8000 воинов из бывших солдат, вандалов, беглых рабов и колонов. Они расположились недалеко от Карфагена, в который к тому времени прибыл сам Велизарий с сотней букцелляриев для спасения положения. В 60 км от Карфагена около города Мамбресы
Стотца был наголову разбит: в начале битвы при сильном противном ветре он стал перестраивать свое войско и не выдержал фронтального удара. Вскоре, однако, Стотца снова собрал под своим знаменем недовольных и смог дать новую битву около города Скалэ-Ветерес выступившему против него римскому войску под командованием Германа, кузена императора Юстиниана (см. Приложение). В ней он и был окончательно разбит и с оставшимися сторонниками ушел к маврам. Однако спустя несколько лет созрел новый мятеж: в 545 г. вакантный магистр и по совместительству дукс Нумидии Гонтарис составил заговор для узурпации власти в Африке. Он вошел в сношения с враждебными империи маврами, и ему удалось даже захватить Карфаген. К нему тут же присоединились бывшие соратники уже погибшего к тому времени Стотцы: 500 римских дезертиров, 80 дезертиров-гуннов и 400 непокорившихся вандалов. Впрочем, через месяц после переворота узурпатор был убит в результате контрзаговора, организованного тагматархом Артабаном, и законность была восстановлена.