В ноябре 536 г. в местечке Регата, недалеко от Террацины (ныне — Терричина), остготские солдаты восстали против Теодата и провозгласили королем своего вождя Витигиса. Узнав о восстании, Теодат пытался бежать, но по приказу Витигиса был убит.
Преемник Теодата, казалось, являлся его полной противоположностью. Храбрый солдат незнатного происхождения, Витигис гордился своими воинскими доблестями. Однако энергичный и мужественный на поле сражения, он проявил себя посредственным полководцем и заурядным политиком. Первоначально приход к власти Витигиса, пользовавшего поддержкой широких слоев готских воинов и пошедшего на сближение с готской партией, вселил большие надежды в готов. Но его стратегический план в борьбе против Велисария оказался неудачным. Вместо того, чтобы наступать, Витигис отступил из Рима в Равенну, оставив «Вечный город» византийцам. Стремясь обезопасить свой тыл, он вступил в переговоры с франками, закончившиеся уступкой им Прованса и уплатой большой дани. Но Меровинги вели двойную игру и, на словах обещая помощь Витигису, на деле не расторгали своего договора с империей. Покинуть Рим Витигиса заставило еще и недоброжелательное отношение к готам римского сената, католического духовенства и самого населения города. Выходец из солдатской среды, новый король во что бы то ни стало хотел придать своей власти законный характер. Он женился на дочери королевы Амаласунты — Матасунте (Матасвинте). Гордая своей знатностью, внучка Теодориха Матасунта ненавидела Витигиса, человека «низкого» происхождения. Она постоянно интриговала против мужа и вместе со знатными готами и римлянами устраивала заговоры против него в пользу византийского императора. Оторвавшись от простых солдат, Витигис не был принят и высшей знатью. Пока король в Равенне справлял брак с Матасунтой, время для наступления против Велисария было потеряно. Стремительным броском Велисарий подошел к Риму и 10 декабря 536 г. без боя овладел им. Активную помощь византийцам при этом оказали знатные заговорщики в Риме во главе с папой Сильверием и сенатором Фиделием. Массы римлян, ненавидевшие готов, сочувственно встретили их изгнание из древней столицы и освобождение oт власти готских королей.
Византийцы сумели захватить также многие важные пункты Южной и Средней Италии. В Средней Италии ими были захвачены города Нарния (ныне — Нарни), Сполеций (ныне — Сполето) и Перузия (ныне — Перуджа). Весной 537 г. огромная армия остготов подошла к Риму. Началась осада. Положение Велисария было очень тяжелым: он располагал сравнительно небольшим гарнизоном в 5 тысяч воинов. В городе из-за голода и болезней росло недовольство. Обещанные императором подкрепления не прибывали. Осада длилась четырнадцать месяцев. Но все усилия Витигиса взять Рим были тщетны, и в марте 538 г. он снял осаду. Его принудили к этому начавшиеся в войске болезни и голод, а также умелый маневр византийцев, пославших в рейд в Пицен, по тылам готов, кавалерийский отряд полководца Иоанна, разграбивший эту область и захвативший в плен жен и детей готских воинов, ушедших в поход. Отряд Иоанна взял Ариминий (ныне — Римини) и угрожал самой Равенне. Еще два года продолжалось сопротивление готов, чему способствовали разногласия, возникшие между Велисарием и посланным к нему на помощь с 7-тысячной армией евнухом Нарсесом. В 539 г. Юстиниан принужден был отозвать Нарсеса из Италии и вновь передать все ведение войны в руки Велисария.
В это время активизировалась и дипломатия готов. В поисках союзников против Византии Витигис заключил соглашение с лангобардами. Весной 539 г. он тайно отправил послов к персидскому шаху Хосрову I Аношарвану с целью разжечь старую вражду между Византией и Ираном. Готы имели успех. Персидский шах стал готовиться к войне против Византии и весной 540 г. нарушил «вечный мир». Однако спасти Витигиса от разгрома Сасанидам не удалось. В это же время в войну готов с византийцами вмешалась третья сила: франки короля Австразии Теодеберта с большим войском перешли Альпы и внезапно вторглись в Лигурию, а затем напали как на остготов, так и на византийцев и опустошили ряд областей на севере страны. Летом 539 г., на обратном пути, франки завершили свои кровавые подвиги разрушением города Генуи.