Během vnitřních bojů o moc ve čtvrtém a pátém století se Římská říše natolik oslabila, že poté podlehla výbojům germánských kmenů přicházejících ze Střední Evropy. Při rozdělení římské říše na západořímskou a východořímskou Tunis zpočátku patřil pod západořímskou. Germáni při stěhování národů byli ale velmi pohybliví, a tak germánský kmen Vandalů prošel na své cestě od Rýna přes dnešní Francii, Španělsko (zde obýval kraj „Vandalusii“), Marokoa Alžírsko až do oblasti Tunisu. Kartágo Vandalové dobyli a zhruba století zde vládli. Tunisko použili jako základnu k dalším výbojům a nakonec dobyli a vyplenili i samotný Řím. Z této události vychází dnešní označení „vandal“, pro toho, kdo něco brutálně ničí.

Po smrti vládce Vandalů Genserica obsadila Tunisko vojska byzantinského císaře Justiniána. Tunisko bylo pak po zhruba sto padesát let součástí Byzantské říše.