Theodosius is thought to have been educated in Oria by Eastern hermits and monks and may have been a young courtier at the Imperial Court of Constantinople.

Theodosius seems to have come back while Hadrian was still alive, with many riches and likely a communication from emperor Basil I, for which he was thanked by Pope Stephen V.[3][4] As a reward, he received some relics of Chrysanthus and Daria for whom he erected a church that might have been the predecessor of the current cathedral.

[4] Around the same time, he deposited the relics of St Barsanuphius, a Gazan hermit, in a chapel he built close to the porta Hebraica.

There is a didactic inscription in the crypt of the church of San Francesco da Paola that mentions the event, which was later built on top of the chapel.

[6] Theodosius was considered a patron of his city for his diplomatic and building activity, and his deeds were perpetuated in local history and tradition, similar to other bishops at the time such as Donatus of Zadar.