In the fifth century, the new tribal federation of the Laguatan threatened Roman Cyrenaica from the east and south. Texts like Epistle 73 by Synesius of Cyrene, written in 409, describe the problems of the inhabitants, who felt abandoned by the central government. Probably, this was a correct evaluation, because it appears that there were only small garrisons in the area. By the end of Synesius' life, the nomadic tribes were close to seizing the province, as is indicated in the lamentation that is known as the Catastasis (413).
We do not know how far the Laguatan were able to proceed. It is certain that the great city of Cyrene was abandoned, but it is likely that the ports remained in East-Roman hands, although Ptolemais may have fallen. Incursions by the Vandals, who had conquered the Tripolitana in the west, may or may not have complicated the situation. Looking at things from an imperial point of view, the Byzantine author Procopius describes the situation as "neglected".note[Procopius, Buildings 6.2.1.]
Still, the province survived. Procopius tells that the Byzantine emperor Justinian (r.527-565) sent troops to the Cyrenaica - perhaps to reinforce troops that were still holding out against the nomads, perhaps to reconquer the ancient province. However that may be, from now on, there were permanent garrisons in Paraetonium (modern Marsa Matruh) and Antipyrgon (Tobruk).
The date of this reorganizing of the province is not known, but we know that general Belisarius reconquered left for Carthage in 533, which proves that by then, Constantinople had an interest in the southern Mediterranean. It is also known that the city of Theodorias was founded in 539. This suggests that the renewal, or Ananeosis, took place in the 530s.
The garrisoning of Paraetonium and Antipyrgon was not the only military measure. According to Procopius, the troops sent by Justinian also fortified Ptolemais, Taucheira/Arsinoe, Berenice/Euesperides (modern Benghazi), two monasteries, and a port called Boreum.note[Procopius, Buildings 6.2.] Probably, several buildings in the port of Naustathmus belong to the Ananeosis too.
Similar measures were taken in the Tripolitana, where Byzantine fortifications can still be seen in Sabratha and Lepcis Magna. Often, the old architectural elements were reused in the new walls ("spolia").