Życie religijne w Bochni od stuleci koncentrowało się w kościele św. Mikołaja. Przed nadaniem praw miejskich w 1253 r. istniał w Bochni drewniany kościółek pod wezwaniem św. Mikołaja, ufundowany przez księżnę Grzymisławę, matkę Bolesława Wstydliwego. Tradycja i zapiski w księ­gach parafialnych mówią, że na jego miejscu w 1253 r. żona księcia, Kinga, ufundowała duży kościół murowany pod wezwaniem św. Mikołaja.

Nieokreślone prace, budowa kościoła lub jego przebudowa były być może związane ze sta­ra­niem kolatora bocheńskiej fary – Kazimierza Wielkiego około 1353 r.

 W 1440 r. kościół spłonął doszczętnie. Odbudowę, usytuowanego w tym samym co poprzednio miejscu budynku ukończono ok. 1445 r., w okresie późnego gotyku. Był to jeden z największych kościołów, jakie wzniesiono w owym czasie na prowincji.

Nowe wnętrze uzyskało układ halowy – czte­ro­przę­sło­wy ze stosunkowo długim, również czte­ro­przę­sło­wym, trójbocznie zamkniętym prezbiterium, przy którym wzniesiono od północy nieregularną przybudówkę mieszczącą zakrystię oraz jednoprzęsłową kaplicę pod wezwaniem 11 tysięcy dziewic, przemianowaną później na św. Kingi. Wysoko osadzone sklepienie (zapewne krzyżowe) wspierało się na bocznych filarach, które do dziś tkwią w ciężkiej barokowej obudowie. Poszczególne przęsła wydzielały ostrołukowe arkady, powodując silne rozświetlenie wnętrza.

Zachowany gotycki szczyt zachodni, o trójstrefowej dekoracji z tynkowanych blend pochodzi z przełomu XV i XVI w. Posiada urozmaiconą formę, złożoną z motywów dwu- i trójlistnych mas­wer­ków oraz łuków w formie oślego grzbietu. Ten bogaty szczyt nie znajduje odpowiednika w ar­chi­tek­tu­rze Małopolski, wskazuje natomiast na jego relacje z gotykiem północnym.

W 1655 roku, w czasie drugiej wojny szwedzkiej, miasto przeżyło wielki pożar. Pastwą ognia padł gotycki dach, runęły sklepienia nawy górnej i naw bocznych oraz przepadła znaczna część wyposażenia. Z pożogi ocalało jedynie prezbiterium z głównym ołtarzem, mury, fasada zachodnia oraz kaplica św. Kingi. Świątynia długo nie mogła podnieść się z ruin, gdyż na barkach zubożałego mieszczaństwa spoczywał trud odbudowy zniszczonego miasta. Dlatego też odbudowa kościoła prowadzona była kosztem króla Jana Kazimierza, który nie tylko zabiegał o szybkie ukończenie prac budowlanych oraz o dotacje dla kleru, lecz również ingerował w formę nabożeństw, uro­czysto­ści pogrzebowych i procesji. Odbudowa kościoła została zakończona w roku 1665. Zgodnie z du­chem czasu kościół przebudowany został w panującym wówczas stylu barokowym. Przekształceniu uległo wnętrze kościoła. W miejsce pierwotnych filarów i arkad międzynawowych wstawiono ma­syw­ne, półkoliste arkady filarowe, wspierające sklepienia kolebkowe z lunetami i kolebkowo-krzyżowe o przęsłach wydzielonych szerokimi gurtami. Ściany i filary opięto pilastrami, a na sklepieniach umieszczono skromną dekorację stiukową z motywem czworoliści.

W latach 1762–1775 wprowadzono do wnętrza kościoła wystrój barokowo-rokokowy autorstwa Piotra Korneckiego i jego warsztatu, w tym ołtarz główny, ołtarze boczne, ambonę, kilka obrazów i feretronów. W 1769 r. Kornecki wykonał na ścianie tarczowej prawej nawy malowidło przed­sta­wia­ją­ce św. Kingę.

 W 1777 r. kościół odrestaurowano z subwencji salinarnej oraz dobudowano do prezbiterium od strony południowej kaplicę na wzór kaplicy w bocheńskim kościele dominikanów, specjalnie dla pomieszczenia cudami słynącego obrazu Matki Boskiej. Kaplicę założono na planie prostokąta z dwoma przęsłami o sklepieniach krzyżowych z gurtami. W tym czasie kościół pozyskał również sprzęty pochodzące ze skasowanych klasztorów bocheńskich – dominikanów i bernardynów, m.in. obraz Matki Boskiej Bocheńskiej wraz z ołtarzem, portal i kratę do kaplicy, figury św. Jacka, ołtarz Matki Boskiej Szkaplerznej, kilka feretronów, obrazów ołtarzowych, relikwiarzy i paramentów. Natomiast w 1790 r. Józef Kornecki, wraz z nieznanym z nazwiska pomocnikiem, Michałem, wykonał niezachowaną polichromię kaplicy Matki Boskiej Bocheńskiej.

W XIX w. stan techniczny świątyni był zły, a drobne prace remontowe nie rozwiązywały pro­ble­mu. Dopiero w 1845 r. odnowiono kaplicę św. Kingi, w której Karol Mirecki wykonał polichromię (nie zachowana). Natomiast w 1846 r. wzniesiono niewielkie kruchty przy wejściach bocznych, w miejsce wcześniejszych drewnianych. W tymże roku sprawiono nową Drogę Krzyżową namalowaną przez Karola Mireckiego, a w 1847 r. poddano konserwacji organy (Roman Ducheński).

 W 1854 r. przebudowano sygnaturkę podług projektu Marcina „Lelewela” Borelowskiego, na­da­jąc jej neogotycki charakter. Dobudowano również małe piętro nad zakrystią z przeznaczeniem na skarbiec oraz zmieniono pokrycie dachu. Dotychczasowe gonty zastąpiono żelazną blachą, zamienioną w początku XX w. na dachówkę.

 W 1860 r. Karol Banach wykonał nie zachowaną polichromię w kaplicy Matki Boskiej Bo­cheń­skiej w miejsce wcześniejszej, autorstwa Józefa Korneckiego.

 W latach osiemdziesiątych XIX w. Jan Matejko zaprojektował wystrój kaplicy bł. Kingi – witraż, stalle, ołtarz, obraz Kingi oraz polichromię ścian wykonaną w 1890 r. przez Antoniego Tucha. Pracami nad regotycyzacją kaplicy kierował architekt Tadeusz Stryjeński.

Za proboszczowania ks. infułata Stanisława Wójtowicza (1959–1984) świątyni groziło nie­bez­pie­czeń­stwo zawalenia. Przyczyną były szkody górnicze. Wykonano wówczas wieniec żelbetowy, ściągi dolne pod posadzką oraz ściągi górne ponad sklepieniem. Dobudowano jeszcze jedną podporę dla ratowania kaplicy Matki Bożej. Zbudowany został nowy chór muzyczny dostosowany do stylu kościoła, a kamienne kolumny zostały usunięte. W latach 1960–1965 kościół otrzymał nową poli­chro­mię i ogrzewanie.

Za proboszczowania księdza Karola Dziubaczki (1984–1992) kościół otrzymał nową instalację elektryczną.

W latach 1993–2015, za proboszczowania ks. Zdzisława Sadko, kościół św. Mikołaja wzbogacił się o nowe inwestycje i godności. Wymieniono laskowania okienne i przeołowiono witraże go­mół­ko­we, założono latarnie wokół kościoła, odnowiono polichromie wnętrza, wstawiono ławki przyścienne wraz z zaplecznikami, zamontowano drzwi spiżowe, ułożono nowego ciągi komunikacyjne wokół kościoła, zrobiono iluminację świątyni, wyremontowano zabytkowy żyrandol z 1848, a także od­two­rzo­no nowe mniejsze żyrandole. Zakrystia otrzymała nowe umeblowanie, dokonano kon­ser­wa­cji ołtarzy, ambony i stalli. Wybudowano nową plebanię, Plac Sanktuaryjny i wy­re­mon­to­wa­no dawne kino parafialne, przekształcając je w Oratorium św. Kingi i wzniesiono Aulę św. Mikołaja. W roku 2008 rozpoczęto remont dachu i wieżyczki.

Kościół św. Mikołaja otrzymał też nowe godności. Ojciec Święty Jan Paweł II 8 listopada 1997 roku podniósł kościół św. Mikołaja bpa do godności „Bazyliki Mniejszej”. W dniu 10 października 1998 roku nastąpiło uroczyste ogłoszenie przez Nuncjusza Apostolskiego w Polsce abpa Józefa Kowalczyka. W roku 2003, na 750-lecie powstania parafii, Biskup Tarnowski Wiktor Skworc podniósł kościół św. Mikołaja w Bochni do godności Kolegiaty i erygował Kapitułę Kolegiacką pod we­zwa­niem Matki Bożej Różańcowej. Sanktuarium Matki Bożej otrzymało też od papie­ża Jana Pawła II formularz Mszy św. „o Matce Bożej Bocheńskiej”, a także kielich, w którym sprawował Najświętszą Ofiarę, ornat i dużą świecę.

Na podstawie:
ks. Stanisław Wójtowicz, Kościół parafialny w Bochni, s. 8-16;
Jerzy Wyczesany, Wystrój artystyczny kościoła św. Mikołaja w Bochni, s. 6-14;
Jan Flasza, Bochnia. Przewodnik po mieście;
ks. Zdzisław Sadko, Różańcowa Matka Boża Bocheńska, s. 60-62;
Kronika Parafialna.