En cambio Teudis no pudo impedir que el Imperio bizantino, después de haber puesto fin al reino de los vándalos del norte de África, se apoderara en el año 534 de Ceuta (Septem), que estaba defendida por una guarnición visigoda —se desconoce el momento en que los visigodos habían tomado esta ciudad situada al otro lado del estrecho de Gibraltar—.