A város legősibb lakott helyén már a XIV. században állt egy román templom. Ennek a helyére rendelte el Nagy Lajos király a ma is megtekinthető, Szent Miklós Bazilika építését. A munkálatok 1380-tól 1421-ig tartottak. Eredeti felépítése szerint háromhajós, kéttornyú homlokzattal ellátott, barokk oldalkápolnákkal rendelkező, későgótikus bazilika volt. Hosszúsága 60 méter, szélessége 31 méter, főhajójának magassága pedig 18 méter. Az évszázadok során persze sokat változott.
1543 és 1820 között az esztergomi érsek székesegyháza volt. Ebben az időben – egész pontosan 1618-ban – rendelte el Pázmány Péter érsek az átépítését. A bazilika barokk oldalkápolnákkal, barokk kórussal és orgonával, több új oltárral bővült, valamint kicserélték a szószéket, a padokat és a padlót. Egyúttal az épület külső körvonalai is megváltoztak. A műveletek 1630-ra fejeződtek be.
Egy későbbi átalakítás során, mely 1739-től 1781-ig tartott, az épület északi részén, barokk stílusban egy nyolcsarkú kápolnát hoztak létre. Máig itt, azaz a Szűz Mária oldalkápolnában található a Könnyező Mária című kegykép, melyet 1546 óta tisztelnek, mint a város oltalmazóját, s ami miatt zarándokhellyé vált a bazilika. A legenda szerint mind ezidáig négyszer látták könnyezni. Első ízben a párkányi csata előtt, 1663-ban, másodszor 1708. július 5-én, harmadszor 1708. augusztus 8-án, végül 1708. augusztus 15-én. Utóbbi három eset a kuruc csapatok számára nehéz napokhoz köthető. A kegykép egy, a római Szent Elek- és Bonifác- templomban található festmény másolata, melyet Forgách Ferenc, későbbi bíboros-érsek készíttetett és ajándékozott a Szent Miklós-templomnak a XIV. században.