Belisarius generobrede Leptis Magna i Roms navn ti år senere, og i 534 e.Kr. ødelagde han
Vandalernes kongerige. Leptis blev en provinshovedstad i det østlige romerske rige (se det byzantinske rige), men kom aldrig sig fra den ødelæggelse, som berberne påførte byen. Det var stedet for en massakre af berber høvdinge af Leuathae stammeforbund af de romerske myndigheder i 543 CE. Historikeren Theodore Mommsen skrev at byen under byzantinsk styre var fuldt ud kristen. I løbet af tiåret 565-578 e.Kr. begyndte kristne missionærer fra Leptis Magna endda at flytte igen blandt Amazigh-stammerne så langt sydpå som Fezzan i den libyske ørken og omvendte Garamantes. Men byens forfald - forbundet endda med Saharaens ørkendannelse - fortsatte, selv om der blev bygget nye kirker, og på tidspunktet for den arabiske erobring af Tripolitanien i 650'erne var byen næsten forladt bortset fra en byzantinsk garnison.