On pense que l’église fut fondée par la sœur de Théodose II (408-450) au Ve siècle et dédiée à l’apôtre saint André qui apporta son aide à l’installation de la première communauté chrétienne de Byzance. Plus tard elle fut dédiée à saint André de Crète qui fut martyrisé lors du règne de l’iconoclaste Constantin V Kopronymos (741-775). Basile Ier la fit restaurer au IXe siècle. En 1261, au départ des Latins qui l’avaient partiellement détruite, c’est la nièce de Michel II Paléologue, Théodora, qui la fit reconstruire et agrandir. L’église fut convertie en mosquée par le grand-vizir Koca Mustafa Pacha sous le règne de Selim I (1512-1520).
Il ne reste pas grand chose des structures d’origine. L’intérieur a été plâtré et un portique a été ajouté. Il est possible de voir quelques colonnes de l’époque byzantine.
Un arbre magique, plusieurs fois centenaire, est planté dans la cour. Une chaîne entoure le cyprès et la légende dit qu’elle met un terme miraculeusement à toute dispute.