Андрей Стратилат служил римским военачальником при императоре Максимиане. Когда шла война с Сирией, он получил титул «стратилат», то есть главнокомандующий, — отсюда и прозвание, с которым он вошёл в святцы.

Выступая против персов с небольшим отрядом, святой Андрей уже веровал во Христа, хотя и не был ещё крещён. Его воины оставались язычниками. Перед сражением он говорил им, что языческие боги — это бесы, и проповедовал истинного Бога. Небольшой отряд, уповая на помощь Божию, обратил в бегство многочисленное персидское войско.

Победа обернулась доносом. Завистники сообщили правителю Антиоху, что победитель — христианин и обратил в свою веру подчинённых. На суде святой исповедал Христа и был подвергнут пыткам, а его воинов распяли на деревьях — но ни один не отрёкся. Император, опасаясь возмущения в войске, отпустил военачальника с дружиной, а тайно приказал под каким-нибудь предлогом казнить каждого поодиночке. Выйдя на свободу, военачальник привёл своих людей в Тарс. Там все они крестились, и там же, в ущелье Тавра, их настигла смерть.

Перед казнью святой молился о тех, кто станет чтить память его дружины, и просил у Господа целебного источника на месте, где прольётся их кровь. Во время этой молитвы мучеников усекли мечом — и в тот же миг из земли пошла вода. Тела погребли епископы Пётр и Нон, крестившие воинов. Один из клириков, много лет мучимый злым духом, испил этой воды и тут же выздоровел. Слух об этом разошёлся по окрестностям, и люди начали приходить к источнику за помощью. Мученическая кончина святых относится примерно к 302 году, а число пострадавших с Андреем воинов предание называет точно — 2593.

Икону мученика Андрея Стратилата дарят военным, охранникам, спасателям — всем, кто отвечает за людей и работает в команде. Берут её и носящие имя Андрей.