Возможности набора войска были очень ограничены; наряду с личной гвардией главнокомандующего Велизария, которого сопровождали его супруга Антонина и историк Прокопий, армия насчитывала лишь 10 000 пехоты и 5000 всадников. Однако было собрано значительное количество военной техники и предоставлен в распоряжение довольно большой флот из 500 кораблей. Когда экспедиция началась летом 533 г., вследствие этих причин можно было рассчитывать на успех, нанеся удар по центральным областям вандальского королевства. Поспешно собранная экспедиция все-таки вряд ли могла пойти на войну на море. Однако вскоре оказалось, что опасаться контрудара со стороны вандалов было нечего; во-первых, Гелимер, по видимости, не ожидал скорого нападения византийцев, а во-вторых, его руки были связаны набегами мавров, отпадением знатного провинциала Пуденция в Триполитании и восстанием на Сардинии. Таким образом, византийцы появились как раз в тот момент, когда их противники оказались в довольно сложной ситуации, которую можно было использовать. Конечно, Гелимер и сам с почти преступным легкомыслием недооценил образ действий противника и тем самым способствовал его успехам. Не поверив в возможность византийского нападения, он послал элитные войска числом 5000 человек под командой своего брата Таты (Цазона) на 120 быстроходных парусниках на Сардинию, чтобы вновь овладеть островом, отпавшим вследствие измены наместника Годы (королевского раба готского происхождения). Тем самым он не только ослабил свои наземные вооруженные силы, но и скорее всего уже не располагал кораблями для обороны побережья. Естественно, эти обстоятельства пошли на пользу Велизарию. После промежуточной высадки на Сицилии, где остготская королева Амаласвинта даже позволила византийцам закупить провизию и Прокопий предпринял необходимую разведку положения врага, византийский флот отплыл к африканскому берегу. 31 августа 533 г. войска высадились у предгорья Капут Вада (Рас Кабудия) и двинулись в сопровождении флота на север [143]. К ходу экспедиции, до сих пор успешному, вскоре присоединились и преимущества в пропаганде. Велизарий повсюду находил сторонников среди населения провинций, по большей части придерживавшегося ортодоксального вероисповедания, заявлением, что византийские войска пришли только как «освободители» от тирании. Поначалу, пожалуй, этот лозунг был встречен с большим доверием, так как гражданское население еще не познакомилось с грабежами солдат Велизария, а еще меньше с византийскими налогами.
После оказавшейся для него внезапной высадки врага Гелимер потерял много времени на материальную, а также на психологическую подготовку к войне. Столица также осталась беззащитной перед возможным нападением византийского флота, когда Гелимер попытался остановить вражеское продвижение у Децима (около 15 км на юг от Карфагена). Он смог лишь перегородить гавань цепями, взять под стражу византийских купцов, подозреваемых в заговоре, и казнить Хильдериха вместе с его римскими сторонниками. То, что Гелимер чувствовал себя уже крайне неуверенно, явствует не только из направленной вестготскому королю Тевду просьбы о помощи, но и, скорее, из того обстоятельства, что король вандалов послал своего тайного секретаря Бонифация со своей королевской сокровищницей в Гиппоне-Регии, откуда в случае проигрыша войны он должен был отплыть в государство вестготов. И все-таки король предпринимал энергичные попытки окружить византийцев у Децима, южнее Тунисского озера, тремя воинскими отрядами, имея в виду, несомненно, классические античные примеры подобных сражений. Это намерение провалилось, так как вандальские отряды были не очень сильны, а наступательные действия были плохо согласованы. Правда, король достиг тактического успеха, но не использовал его, так как после гибели своего брата Амматы он перестал надлежащим образом заниматься военными делами. Между тем Велизарий перестроил свои войска и конной атакой вечером 13 сентября 533 г. добился легкой победы над Гелимером. Так как Гелимер не мог думать о том, чтобы защищать от врага едва укрепленную столицу, он бежал в направлении Нумидии. Поэтому Карфаген достался византийскому полководцу без боя; там он попытался, также и с помощью мягкого обращения с попавшими в плен вандалами, создать благоприятное для себя настроение и нормализировать течение жизни. Поначалу население, очевидно, ничем не обременялось, а солдатские бесчинства строго карались. В особенности Велизарий заботился о скорейшем восстановлении укреплений. В Византии первые известия о победе вызвали быструю реакцию; жадный до успеха Юстиниан уже в постановлении от 21 ноября 533 г. принял триумфальные имена Alanicus, Vandalicus и Africanus (Аланский, Вандальский, Африканский), что все-таки кажется несколько преждевременным.