Î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, îmbărbătându-i în suferinţele lor.
Istoricul Eusebiu de Cezareea (265-339), care a asistat la 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 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.”
