В сентябре 535 года Велизарий высадился на Сицилии, где, как в Африке, жители распахнули ворота своих городов. На Сицилии было мало готов. Они имели гарнизон в Палермо, но Велизарий занял город внезапной атакой. К зиме весь остров был в его руках. Он как раз собирался направиться в Италию, когда восстание в Африке заставило его пересечь море и провести некоторое время в окрестностях Карфагена.
Тем временем несчастный малодушный Теодахад не делал ничего — только осаждал Юстиниана бесплодными просьбами о мире. Он был, как всегда, совершенно не готов к сопротивлению, когда Велизарий в апреле 536 года переправился через Мессинский пролив и захватил Бруттиум (Бруттий) и Луканию. Готы были настолько обескуражены его беспомощностью, что Эбермунд, правитель Лукании, сдался Велизарию и поступил на императорскую службу со всеми своими людьми. Только дойдя до Неаполя, Велизарий встретил сопротивление; на юге Италии ворота всех городов распахивались, стоило ему коснуться их наконечником своего копья. Но в древнем городе Неаполе был сильный готский гарнизон, и он держался много недель, ожидая помощи. Король Теодахад собрал в Риме большую армию, однако трус не осмелился приблизиться к Неаполю, и 50 000 человек оставались в бездействии, пока 7000 римлян осаждали Неаполь. Наконец город все-таки пал. Отряд исаврийских солдат пробрался в город по неиспользованному акведуку и открыл одни из ворот изнутри. Новость о падении Неаполя довела гнев готов на своего беспомощного короля до точки кипения. На большом народном собрании в Регете, что на территории Помптинских (Понтинских) болот, армия сместила Теодахада, и, поскольку наследников Амала мужского пола больше не было, подняла на щит Витигеса, немолодого уважаемого воина, который завоевал хорошую репутацию во время войн Теодориха. Свергнутый король бежал в Равенну, однако его личный враг устремился в погоню и перерезал ему горло, «как овце», раньше, чем он успел добраться до убежища.
Выбор Витигеса был ошибкой готов. Они ошибочно приняли респектабельность за талант и заплатили за это высокую цену, поскольку не слишком умный ветеран сокрушил все их надежды. Первой ошибкой нового короля стал отвод армии на север — в это время пришло сообщение, что франки переходят Альпы, чтобы разграбить долину По. Он оставил в Риме только 4000 человек и с остальными выступил в направлении Равенны. Когда готская армия покидала Рим, Велизарий двигался на север, собираясь напасть на имперский город. Он оказался в его руках без боя. Готский гарнизон решил, что его предали, оставив среди населения, готового предать его врагу. Римский папа Сильверий и сенат действительно обратились к Велизарию с просьбой избавить их от готов. Когда имперская армия подошла к южным воротам, готы бежали через северные. Их паника представляется непростительной — ведь их было не намного меньше, чем 5000 человек, которых Велизарий привел с собой. Это было 9 декабря 536 года.
Теперь Велизарий стал хозяином Рима, но он знал, что находится в весьма опасном положении. Витигес урегулировал дела с франками, выплатив им 130 000 золотых монет (солидов) и уступив трансальпийские владения в Провансе. После женитьбы на Матасунте (Матасвинте), сестре покойного короля Аталариха, последней представительнице рода Амалов, он решил вернуться и освободить Рим. Весь север Италии дал ему готских воинов, и, собрав под свои знамена стотысячную армию, Витигес весной 537 года двинулся на Рим.
Оборона Рима — величайшее из всех деяний Велизария, прославившее его имя на века. Стена Аврелиана была крепкой, но в распоряжении Велизария было всего 5000 человек. Нельзя было сбрасывать со счетов и неуправляемую массу трусливых горожан, подверженных всякого рода паническим страхам. Все эти рты надо было как-то прокормить, но участвовать в сражениях они вовсе не собирались. Едва ли житель Рима стал бы помогать византийским войскам. В середине марта готы подошли к стенам города и разбили семь лагерей напротив северных и восточных ворот. После этого они перерезали все акведуки, по которым велось снабжение города водой, и начали сооружать осадные машины. Король Витигес, продемонстрировав обычное для него отсутствие основательности и глубины, не произвел адекватных приготовлений к блокаде южной стороны города и прекращению его связей с Остией и Неаполем. Поэтому на протяжении всей осады в Рим по ночам регулярно прибывали конвои с продовольствием и подкреплением. Им удавалось без особого труда обходить аванпосты, выставленные Витигесом со стороны Тибра и Кампаньи.