Muceniţa Teodosia era din oraşul Tir, din Fenicia. În anul 308, pe când se afla în Cezareea Palestinei, a mers la palatul dregătorului Urban, la temniţa unde erau înlănţuiţi creştinii, şi-i îmbărbăta pe aceştia pentru suferinţele lor pentru numele Mântuitorului Iisus Hristos.
Istoricul Eusebiu de Cezareea (265-339), care a văzut mucenicia Sfintei Teodosia, scrie: „Prelungindu-se până la cinci ani prigonirea creştinilor de către păgânii închinători la idoli, în ziua a doua a lunii aprilie, chiar la praznicul Învierii Domnului, în cetatea noastră, adică în Cezareea Palestinei, o fecioară credincioasă, de neam din Tir, care nu avea încă 18 ani, s-a apropiat de cei legaţi pentru Hristos şi le grăia lor cu îndrăzneală despre Împărăţia lui Dumnezeu.
Apoi le-a urat de bine, rugându-i să o pomenească şi pe ea înaintea Domnului, când vor sta în faţa lui Dumnezeu, după sfârşitul nevoinţei lor muceniceşti. Iar ostaşii care păzeau, auzind-o pe fecioară grăind asemenea cuvinte celor legaţi pentru Hristos, au prins-o ca şi cum ea ar fi făcut un mare rău şi au dus-o la dregătorul Urban. Acesta a poruncit să o întindă pe roată şi să-i sfâşie coastele şi sânii cu gheare de fier, până la oase. Sfânta a suferit toate aceste chinuri cu bucurie, iar dregătorul, văzând-o că încă este vie, a poruncit să fie aruncată în mare şi înecată. Şi astfel s-a mutat la Domnul.