Prema crkvenom predanju, Andrej je od rođenja bio nijem. Kada su ga roditelji odveli u hram i pričestili, dječak je progovorio, što se u pravoslavnoj tradiciji smatra neposrednim dokazom sile i blagodati božanskog pričešća.

Sa 14 godina otišao je u Jerusalim, gdje je stupio u manastir. Svojim oštrim umom, predanim podvigom i duhovnom zrelošću brzo je nadmašio i znatno starije monahe, postajući uzor cijeloj zajednici. Prepoznavši njegove izuzetne sposobnosti, tadašnji jerusalimski patrijarh uzeo ga je za svog pismovoditelja.

Pošto patrijarh nije mogao lično da prisustvuje saboru koji se održavao u Carigradu, Andrej je otišao umjesto njega. Na saboru je pokazao izuzetnu darovitost, rječitost, nepokolebljivu revnost prema vjeri i neobičnu razboritost, čime je dao značajan doprinos očuvanju i učvršćivanju pravoslavnog učenja.

Nakon što je pomogao da se pravoslavna vjera učvrsti, Andrej se vratio svojim dužnostima u Jerusalimu. Kasnije je izabran i postavljen za arhiepiskopa ostrva Krita. Kao arhijerej, bio je duboko voljen u narodu, a predanje bilježi da je svojim molitvama činio mnoga čuda.

Sveti Andrej Kritski ostavio je neizbrisiv trag u hrišćanskoj himnografiji. Napisao je brojne poučne knjige, pjesme i kanone, među kojima je najpoznatiji Veliki kanon (Kanon Andreja Kritskog), koji se čita u četvrtak, u petoj nedjelji Časnog posta.

Vraćajući se jednom prilikom iz Carigrada, predosjetio je svoju smrt. To se ubrzo i dogodilo — preminuo je na lađi dok je plovila blizu ostrva Mitilene.