Císař Licinius (307 - 324), který vládl ve východní části římské říše, pokračoval, jako jeho předchůdce, v pronásledování křesťanů. Když však viděl, že se mu všechny křesťany nepodaří vyhubit, rozhodl se pronásledovat pouze významné osobnosti.
V té době byl představeným v Heraklei Teodor, vojenskou hodností stratilát. Ten získal svým příkladem mnohé pohany pro křesťanství.
Když se o Teodorovi dozvěděl Licinius, poslal k němu své sluhy, aby stratiláta předvedli. Teodor věděl, že nadešla doba jeho zkoušky. Protože chtěl ve městě utvrdit víru, rozhodl se pro lest. Nejdříve stále oddaloval svůj odchod k císaři a pak mu poslal dopis, ve kterém jej žádal, aby se dostavil do Heraklee: „... mnozí zde opouštějí víru otců ...ve městě je zmatek ...proto sám, císaři, vezmi své bohy a přijď sem ...učiň to ze dvou důvodů: abys uklidnil národ a abys potvrdil dřívější víru.“
Císař dopis přečetl a zaradoval se. Nemeškal, vzal vojsko, kněze a bohy a vypravil se do Heraklee. Jakmile dorazil do města, chtěl po Teodorovi, aby s lidem obětoval modlám. Stratilát jej však požádal, aby mu nejdříve dal své bohy a on je na tři dny vystaví ve svém domě. Císař mu vyhověl a Teodor v noci sochy rozbil na malé částečky a zlato z nich rozdal chudým.
Licinius se dozvěděl o podvodu, rozhněval se a vydal Teodora strašným mukám. Několik hodin jej bičovali, pak drhli železnými kartáči, pálili ohněm a nakonec ho přivázali na kříž. Ale ani na kříži jej mučitelé nenechali v klidu. Rozřezávali mu tělo břitvami, stříleli mu do obličeje šípy, takže přišel o obě oči.
Když si Licinius myslil, že je Teodor mrtvý, nechal ho viset na kříži. V noci se mučedníkovi zjevil anděl, který sňal jeho tělo z kříže a uzdravil jej.
Následující den poslal císař vojáky pro Teodorovo tělo, aby je křesťané nevzali, a chtěl je hodit v železné rakvi do moře. Vojáci přišli ke kříži, ale našli mučedníka zdravého, jak se modlí. Tu oba vojáci uvěřili v Krista. Licinius se o tom dozvěděl a poslal tam tři sta vojáků, aby věřící v Krista zabili. Ale i těch tři sta uvěřilo. A k mučedníkovi se již sbíhali lidé. Když se Leandr, jeden z císařových vojáků, pokusil Teodora zabít mečem, nastalo mezi lidmi pozdvižení. Světec však dav uklidňoval, aby se neprotivili vládci. Když pak císař poslal dalšího vojáka, aby stratiláta sťal, Teodor se pomodlil, uklidnil lid, sklonil hlavu a nechal na sobě vykonat Liciniův rozkaz (r. 319). Jeho utrpení bylo sepsáno přímým svědkem, písařem Jarem.
Ostatky sv. Teodora byly přeneseny r. 319 z Heraklee do Euchaity (vzpomínka 8.6.).
Někteří autoři se domnívají, že životopis sv. Teodora Stratiláta je jen volnou variací života sv. Teodora Tirona, což je velmi pravděpodobné.