Тотила был племянником (сыном брата) остготского короля Ильдебада. Командуя гарнизоном в Тарбезии (современный Тревизо) и узнав об убийстве своего дяди, он готовился сдаться византийцам, когда готы, недовольные слабым Эрарихом, избрали Тотилу королём (в 541 году, вероятно, в октябре). Вскоре убийство Эрариха избавило Тотилу от соперника.
Возможно, что Тотилу — судя по легендам на монетах и некоторым литературным источникам[3] — на самом деле звали Бадуила (Бадуа), что значит «Борец» или «Боец».
В 543 или, более вероятно, в 542 году Тотила посетил в Монте Кассино св. Бенедикта, но предание так исказило этот факт, что невозможно сказать, какую цель король при этом преследовал. По свидетельству автографа папы Григория Великого, святой предсказал Тотиле срок его правления и дату его смерти.
Когда Тотила принял корону, почти весь Апеннинский полуостров находился в руках врагов. Тотила продолжил военный план Ильдебада и чрезвычайно искусно пользовался отсутствием организации и единства командования в имперских отрядах. Юстиниан I, не одобрявший бездействия своих полководцев, послал им в подкрепление отряд персидских военнопленных, присланных Велисарием, и требовал начала военных действий. После неудачной попытки овладеть Вероной императорское войско постыдно должно было снова возвратиться к Равенне. Тотила со всеми силами, какие только мог собрать (пять тысяч воинов), напал на главную часть византийского войска и нанёс ей такое поражение, что разбитый отряд искал спасения в бегстве и за стенами укреплённых городов. Вскоре король одержал новую победу. Он оттеснил византийские войска за По и весной 542 года разбил их при Фавенции (совр. Фаэнца). С помощью удачного манёвра охвата, главную роль в котором сыграли 300 готских конных копейщиков, он рассеял более чем вдвое большее византийское войско. Варвары как готского, так и не готского происхождения толпами переходили на сторону Тотилы, и даже один высокопоставленный букцеллярий Велисария Индульф изменил делу императора. За короткое время готская армия снова выросла до 20 000 человек. Вскоре крупные готские силы взяли Цезену и Петру и осадили город Флоренцию, чтобы освободить себе дорогу на Рим. Отступив перед пришедшим на помощь Флоренции императорским войском, готы отошли на расстояние дневного перехода к северу, в долину Муджелло (Муцелла), где наголову разбили противника. С очевидностью обнаружилось, что готский король владеет военным искусством, которого недостаёт императорским полководцам. Военный план Тотилы, совершенно не понятый византийцами и смутивший их, состоял в том, чтобы, не предпринимая осады крепостей, овладеть всеми открытыми областями, изолировать византийские гарнизоны, сидевшие в городах, и лишить их внешних сношений. Если случай или военная хитрость давала Тотиле во владение крепость, он разрушал её стены и сравнивал её с землёй, дабы впоследствии неприятель не нашёл в ней укрытия.