Den hellige Theodosia er kjent gjennom skriftene til den berømte kirkehistorikeren Eusebius av Caesarea (ca 260-340). I sitt verk «Martyrer i Palestina» (De martyribus Palestinae) forteller han om forfølgelsene under keiserne Diokletian (284-305), hans medregent i vest, Maximian Herkules (286-305) og Maximian Galerius (305-11), som pågikk fra 303 til 310. Han var vitne til mange av henrettelsene og kjente flere av martyrene personlig, inkludert Theodosia.
Theodosia ble født i 289 i Tyros i Libanon. Som attenåring var hun i påsken 307 på besøk i Caesarea i Palestina (Kaisareia Paralios), og da prøvde hun å trøste noen fanger som ventet på å bli dømt. De var trolig kristne, og det virker som om hun ba dem om å minnes henne når de kom inn i Guds herlighet.
Da ble hun arrestert og stilt for retten, og etter ordre fra prefekt Urban ble hun flere ganger torturert. Hennes bryst ble skåret av og hennes sider ble revet opp av jernkroker, og deretter ble hun druknet i havet. Det skjedde den 2. april 307. Alle dem hun trøstet, ble dømt til tvangsarbeid i koppergruvene i Phanaeo, et langvarig og pinefullt martyrium.
Hennes minnedag er 2. april med en sekundær fest den 3. april. Hennes minnedag i øst er 29. mai, men da forveksles hun med den hellige Theodosia, mor til den hellige Prokopius, den første martyren i Caesarea i Palestina, som minnes samme dag. Hun feires samme dag som den hellige Appian, som døde i Caesarea nøyaktig ett år tidligere, den 2. april 306.
Hennes dødsår angis vekselvis til 303, 306, 307 og 308. Øyenvitnet Eusebius sier at hun ble henrettet «i påsken i det femte år av Diokletians forfølgelse, på den andre dag i måneden Zanthikos, på fjerde dag før Nonis Aprilibus». Siden Diokletians forfølgelse begynte med ediktet av 23. februar 303, blir det femte året 307, og martyriet skjedde den 2. april 307.
Den hellige Beda den Ærverdige (d. 735) legger feilaktig hennes martyrium til Caesarea i Kappadokia, noe som følges av den hellige Ado av Vienne (d. 875). Theodosias angivelige relikvier kom til Konstantinopel, og deler av dem kom til Venezia og dominikanerinneklosteret Corpus Christi og til Santa Croce (eller Chiesa della Trinità) i bygningskomplekset San Stefano i Bologna.