Svedectvo o nej podáva jej súčasník, starokresťanský dejepisec Euzébius Cézarejský.

Podľa jeho správy v prenasledovaní kresťanov za cisára Maximiána sa 2. apr. 307 v palestínskej Cézarei konal súd nad kresťanmi. Obžalovaní sedeli pred tribunálom strážení vojakmi. Obďaleč boli diváci, ktorí sledovali priebeh súdu. Medzi nimi bola takmer 18-ročná deva Teodózia, ktorá pochádzala z Týru. V jednej chvíli sa oddelila od divákov a priblížila sa k odsúdencom. Azda ich chcela povzbudiť alebo ich poprosiť o modlitbu.

Ale vojaci sa na ňu vrhli a privliekli ju pred guvernéra. Ten sa rozzúril a rozkázal jej, aby hneď obetovala bohom. Keď nechcela, dal ju mučiť ako zmyslov zbavený. Teodózia prežila hrozné masakrovanie. Vtedy ju dal guvernér hodiť do mora.

Úcta tejto palestínskej mučeníčky sa rozšírila aj na kresťanskom Západe. Ibaže neskoršie správy o jej umučení boli rozšírené o podrobnosti, ktoré sa nenachádzali v pôvodnom Euzébiovom texte.

Staršie martyrológiá a kalendáre uvádzali sv. Teodóziu Cézarejskú na deň 2. apríla. Avšak neskôr sa tak na Východe ako aj na Západe začala sláviť jej pamiatka 29. mája.