Stavba kostela začala po roce 1221 v románském slohu. Ve 13. století, ve válce s Přemyslem Otakarem II. došlo k značnému poškození kostela. Stavební rozvoj dnešního trojlodního gotického chrámu nastal ve 14. století. Klenba byla dokončena v roce 1452 a v tomto roce byl kostel i vysvěcen. Délka vnitřního prostoru je 63,37 m, šířka 22,85 m, výška lodí je 16,02 m, výška presbytáře 18,5 m. Klenba presbytáře je žebrová s 23 svorníky, na kterých jsou znaky rodů, míst a krajů, podílejících se na stavbě chrámu. Vlevo na zdi je nástěnná malba z 19. století s nápisy zde korunovaných uherských králů a královen. Nalevo od presbytáře byla na místě původní gotické sakristie postavena barokní kaple sv. Jana Almužníka, pod níž jsou v kryptě uloženy rakve s ostatky arcibiskupů. Nad oltářem se nachází stříbrná rakev s relikviemi sv. Jana Almužníka. V jižní lodi je gotická křtitelnice z roku 1403 a sousoší sv. Martina z roku 1734 od bratislavského rodáka, sochaře Juraje Rafaela Donnera. Hlavní oltář je z roku 1864 od vídeňského mistra Jana Hutterera. Vež byla původně součástí opevnění a několikrát byla zničena. Naposledy byla opravována a dostavěna po požáru roku 1833 v letech 1835-49 do výšky 87 metrů. Na hrotu věže, ve výšce 85 m je umístěna na podušce 2x2 m pozlacená uherská koruna, vysoká 1,57 m a vážící 300 kg. Pod ciferníky hodin se nachází zvonice. Nejstarším zvonem je zvon Wedderin, odlitý Baltazarem Heroldem v roce 1675. V roce 2000 bylo do věže osazeno dalších 5 nových zvonů, darů okolních států. tyto zvony jsou dílem dílny Marie Tomáškové-Dytrichové z Brodku u Přerova.