Kostel byl pravděpodobně postaven v šestém století za vlády byzantského císaře Justiniána I. (r. 527–565) a je jedním z nejstarších křesťanských kostelů v oblasti Kappadokie a také jedním z nejstarších známých kostelů, které mají kopuli na tamburu vybaveném okny, která osvětlují interiér.[1] Kostel byl možná zasvěcen svatému Řehoři z Nazianzu, jednomu z otců kappadocké církve.[1] Domorodci jej také nazývali klášter svatého Pantaleona (Μοναστήριον του Αγίου Παντελεήμονος);[2] jiné zdroje tvrdí, že se jmenoval Sv. Spyridon.[3]

Ve střední a východní Kappadokii byly v 5. a 6. století standardem kostely s půdorysy ve tvaru kříže.[4] Kızıl Kilise k nim patří a využívá místní kámen sopečného původu tvarovaný do pravidelných bloků vysoce kvalifikovanými pracovníky. Architektonicky nejcharakterističtějším prvkem kostela je jeho centrální kupole, vztyčená nad osmibokým tamburem.[1][5] V něm je osm oken osvětlujících prostor kostela.[1] Jediným pozdějším doplňkem budovy je narthex; jinak si kostel, byť poškozený, stále zachovává původní podobu.[1] Přítomnost mohutných překladů finišovaných vysoce profesionální technikou naznačuje využití jako císařská nebo pohřební kaple. Poutníci procházející Anatolií na cestě do Jeruzaléma starověkou cestou mohli kostel snadno navštěvovat.

Gertrude Bellová (1868–1926), britská archeoložka a spisovatelka, Kızıl Kilise vyfotografovala a změřila v roce 1907.[6]

Kostel byl používán do 1. srpna 1924 turecky mluvícími křesťany z vesnice Sivrihisar, než se odstěhovali do Řecka v rámci výměny obyvatelstva.[2]

V roce 2011 začal program rekonstrukce kostela. Mezinárodní sbírka vynesla 500 000 €. Projekt řídil İsmet Ağaryılmaz, profesor v důchodu, který dříve vyučoval restaurátorské techniky na Technické univerzitě Yıldız.[7][8][9]