La flota oriental, compuesta por 92 dromones que escoltaban 500 transportes, abandonó los puertos de Constantinopla a mediados de junio de 533 y, vía Sicilia alcanzó las costas africanas al cabo de tres meses, desembarcando en la ciudad de Caput Vada, en la actual Túnez, con un ejército de unos 15 000 hombres, más un número indeterminado de tropas auxiliares bárbaras.