Kościół wzniesiono przy starym szlaku handlowym wiodącym z Krakowa do Sandomierza i dalej na wschód – na Ruś i Ukrainę. Co ciekawe, w kościele wschodnim święty Mikołaj był czczony jako patron całej Rusi i podróżujących. Najstarsze wzmianki o świątyni pochodzą z pierwszej połowy XIII wieku. W bulli papieskiej z 1229 roku wspomniano, że była własnością ojców benedyktynów z Tyńca. W 1467 roku zakon przekazał kościół Akademii Krakowskiej.

Budynek pierwotnie romański, po pożarze w 1376 roku zyskał gotycką postać. Kościół spalony podczas oblężenia miasta przez Szwedów, odbudowano w latach 1677–1682. Dzisiejszy ma skromne, barokowe formy, poza gotyckim, wielobocznie zamkniętym i wzmocnionym przyporami prezbiterium, kryjącym zręby romańskiej świątyni.

W trójnawowym wnętrzu, wśród wyposażenia pochodzącego z XVI–XVIII wieku, uwagę przyciąga późnogotycki ołtarz-pentaptyk ze sceną koronacji Matki Bożej, znakomite dzieło krakowskich malarzy z końca XV wieku. Cenna jest też chrzcielnica z brązu z 1536 roku oraz późnorenesansowy nagrobek z białego marmuru i gotycki, schodkowy portal w zakrystii.

Na terenie dawnego cmentarzyku okalającego kościół, stoi jedyna w Krakowie, unikatowa, gotycka figura przydrożna z XIV wieku, tak zwana latarnia zmarłych. Latarnie takie stawiano głównie w średniowieczu przed szpitalami, przytułkami, leprozoriami czyli szpitalami dla trędowatych i cmentarzami, wszędzie tam gdzie można się było czymś zarazić. Ta latarnia stała przy leprozorium przy kaplicy świętego Walentego na Kleparzu, a na teren przykościelny przeniesiono ją w 1871 roku. Innym niezwykłym obiektem jest chaczkar, czyli kamień krzyżowy, w kulturze ormiańskiej tradycyjnie przypominający ważne wydarzenia historyczne i zmarłych. Krakowski chaczkar upamiętnia Ormian, którzy od XIV wieku mieszkali w Polsce. Monument jest poświęcony również ofiarom ludobójstwa dokonanego na 1,5 miliona Ormian w Turcji w 1915 roku.

W świątyni msze odprawiane są w obrządku ormiańskim. Kościół jest też sanktuarium błogosławionej Hanny Chrzanowskiej, której konfesja z relikwiarzem znajduje się w nawie bocznej.