Acesta a trăit în vremea păgânului împărat Maximian, din părţile Răsăritului şi era în dregătoria ostăşească de stratilat, care înseamnă căpetenie de ostaşi, de unde-şi trage şi numele. Năvălind perşii în Siria, Antioh, căpetenie peste toată oştirea, l-a trimis pe Sfântul Andrei, împreună cu alte oşti împotriva duşmanilor. Acesta s-a rugat mult şi-i îndemna şi pe ostaşi să se roage, iar biruinţa le-a întărit multora credinţa în Hristos.
Fiind pârâţi lui Antioh, care era om rău la suflet, crunt la fire şi duşman neîmpăcat al creştinilor, acesta a poruncit să fie aduşi în faţa lui, Sfântul Andrei şi ostaşii, închinători ai Lui Hristos. Mărturisindu-şi credinţa, ostaşii au fost legaţi în lanţuri şi osândiţi să fie surghiuniţi în afară de hotarele Siriei, iar pe Sfânt l-au întins pe un pat de fier ars în foc, dar rămânând nevătămat, s-au gândit să-l osândească la moarte. Socotind însă, că nu este bine ca pe nişte ostaşi slăviţi şi viteji, să-i piardă în mijlocul poporului, a poruncit să-i lase liberi, hotărând să-i piardă, în taină, pentru alte pricini.
Văzându-se liberi, Sfântul Andrei şi ostaşii lui, au mers îndată în Cilicia şi s-au botezat, în credinţa Lui Hristos, dar aflând dregătorul a poruncit să li se taie tuturor capetele, prin sabie. Atunci, au primit cununa muceniciei peste două mii cinci sute de ostaşi, împreună cu Sfântul Andrei Stratilat, crezând în Hristos Dumnezeu.
