Faţă de Preasfânta Născătoare de Dumnezeu, Sfântul Andrei Criteanul nutrea o mare iubire şi o adâncă evlavie. Aceasta o constatăm din imnele pe care i le-a închinat, din cuvintele pe care le-a rostit şi din omiliile pe care le-a scris despre persoana şi sărbătorile închinate ei. Exprimarea acestei dragoste s-a observat şi în construirea măreţei biserici închinate Preasfintei Fecioare, pe care a numit-o „a Vlahernelor”:

„A construit o nouă biserică Preasfintei şi Preacinstitei Născătoare de Dumnezeu, Fecioara Maria, care lăcăş sfinţit şi însufleţit al Cuvântului lui Dumnezeu pe sine s-a făcut. Pe aceasta a numit-o Vlaherne, după biserica cu acelaşi nume. Şi a stabilit în biserica aceasta preoţi vrednici şi cu teamă de Dumnezeu din ceata monahilor, ca să cânte şi să-L slăvească pe Dumnezeu, ca dar de schimb pentru bunătatea şi pentru toate cele ce vin de Sus, de la Dumnezeu”.

(Simeon Koutsa, Plânsul adamic: canonul cel mare al Sfântului Andrei Criteanul, trad. de Alexandru Prelipcean, Ed. Doxologia, Iași, 2012, pp. 24-25)