Fulgentius was exiled to Sardinia shortly after his episcopal ordination in AD 508 (I follow the chronology of A. Mandouze in PCBE Afrique: Fulgentius 1), he returned shortly to Africa between AD 516/517 and AD 518/519 and was again exiled until the death of King Thrasamund in AD 523.
Felicianus probably returned from Sardinia together with Fulgentius, and he was ordained his successor in AD 534.