Флот шел вдоль морского берега, не удаляясь от него, с задачей обеспечивать правое крыло армии. Вперед Велизарии выслал разведывательный отряд численностью 300 воинов, которому было приказано двигаться в 3,5 км от главных сил с задачей обнаружить движение противника и предупредить свои войска, чтобы они могли вовремя перестроиться из походного порядка в боевой. Отряд массагетов составил левую колонну, которая двигалась параллельно колонне главных сил на расстоянии в те же 3,5 км. Основные силы возглавил сам Велизарий. Они наступали вдоль морского берега, стараясь не терять из виду свой флот.

Будучи хорошим политиком, Велизарий строго запретил солдатам любые агрессивные действия против местного населения. Таким образом, ромеев (так себя называли византийцы) жители встречали как освободителей, снабжали их продовольствием. Византийский военачальник также установил дружеские связи с имущими слоями населения, что еще более укрепило положение его армии. Дневные переходы армии не превышали 14 км. Через Лейту и Адрамит ромеи вышли в местность Грассу, находившуюся в 63 км от Карфагена, где произошла первая стычка разведчиков.

Гелимер отряду под командованием своего брата Аммата приказал у Дециума (в 12,5 км от Карфагена) окружить и уничтожить авангард римлян. Второй отряд из 2 тысяч всадников возглавил племянник Гелимера Гивамунд. Он должен был атаковать левую колонну противника на солончаках. Сам Гелимер с главными силами собирался форсированным маршем в обход левой колонны византийцев выйти к ним в тыл, напасть на главные силы римлян и отрезать их от флота. Проблема Гелимера заключалась в том, что на пересеченной местности ему не удалось обеспечить нормальной связи между отрядами, скоординировать их действия. Основные события под Дециумом произошли 14 сентября 533 г.[35]

Аммат, еще не собрав своего отряда, «с малым числом и то не отборных воинов» раньше назначенного времени прибыл в Дециум. Остальные воины отряда по дороге из Карфагена шли в беспорядке группами по 20–30 человек. В это время разведывательный отряд византийцев подошел к Дециуму. В бою между передовыми отрядами Аммат был убит. Оставшиеся в живых вандалы бежали по дороге в Карфаген и увлекли за собой весь отряд. Византийцы разведывательного отряда преследовали бежавших и дошли до ворот Карфагена.

В это время отряд вандалов под командованием Гивамунда вышел в район солончака, находившегося влево от карфагенской дороги и в 7 км от Дециума. Здесь отряд был атакован массагетами и уничтожен. Если бы Гивамунд и Аммат поддерживали нормальную связь, то первый мог бы вовремя прийти на помощь последнему в Дециум. Тогда византийцам пришлось бы несладко. А так оба отряда вандалов были разбиты превосходящими силами противника.

Вскоре главные силы римлян были уже в 6 км от Дециума, оторвавшись, таким образом, на значительное расстояние от своего флота. Велизарий нашел место, удобное для устройства укрепленного лагеря, приказал вырыть ров и расположил в лагере обоз и пехоту. Навстречу вандалам выступила конница ромеев с тем, чтобы выявить силы противника, а затем вступить в бой всем войском. Вперед были высланы федераты, отряд которых имел задачу установить местонахождение противника.

Вскоре этот отряд достиг Дециума. От местных жителей члены отряда узнали о бое разведчиков двух армий. К югу от Дециума федераты заметили тучи пыли, через некоторое время показалась и сама конница вандалов. Отправив Велизарию просьбу о помощи, федераты стали спорить о том, что делать дальше. Одни считали, что надо атаковать приближающегося противника, другие предлагали подождать подкреплений. Тем временем вандалы приблизились к отряду.