Sfânta Teodosia a fost originară din Tir (Fenicia). Potrivit lui Evsevie, episcopul Cezareei Palestinei, martor ocular, Sfânta Teodosia s-a apropiat de creştinii închişi în temniţă pentru că nu mai jertfeau idolilor şi i-a întărit în mucenicia lor. Din această cauză, sfânta a fost dusă de soldaţii care păzeau temniţa înaintea judecătorului. Acesta auzind cele întâmplate, a poruncit să i se lege o piatră de gât şi să fie aruncată în mare. Prin purtarea de grijă a lui Dumnezeu, îngerii au adus-o la mal nevătămată.
Când ea s-a înfăţişat înaintea judecătorului, purtând în mâini piatra care fusese legată de grumajii ei, el a poruncit ca să i se taie capul. în următoarea noapte, Teodosia s-a înfăţişat părinţilor ei înconjurată de o lumină cerească negrăită, şi de multe alte fecioare, şi ele mântuite, şi le-a zis: “Vedeţi voi ce mare este slava şi harul Hristosului meu, de care voiaţi să mă lipsiţi?” Ea a rostit către părinţii ei aceste cuvinte, pentru că aceştia o opriseră să-şi mărturisească pe faţă credinţa în Hristos şi să se faca mucenică.
Teodosia a luat cu cinste cununa mărturisirii în anul 308, la vârsta de numai 18 ani.
