Są przypuszczenia, że parafia w Rychwałdzie istniała już w 1335 r., jednakże dane historyczne mówią o roku 1472 jako dacie jej powstania. Pierwszy kościół, fundowany przez właściciela Ziemi żywieckiej, Mikołaja Komorowskiego, był drewniany. Konsekrował go biskup krakowski Erazm Ciołek w 1547 r. W 1644 r. właścicielka Ślemienia, Katarzyna z Komorowskich Grudzińska, darowała do kościoła rychwałdzkiego obraz Matki Bożej, który początkowo umieszczono w bocznym ołtarzu. Biskup krakowski Mikołaj Oborski dekretem ogłosił obraz jako cudowny i polecił szerzyć jego kult. 22 października 1678 r. obraz przeniesiono do głównego ołtarza.

W połowie XVIII w. wybudowano w Rychwałdzie nowy murowany kościół w stylu barokowym, który konsekrował biskup Franciszek Potkański 2 lipca 1756 r. W tym samym dniu przeniesiono obraz Matki Bożej do nowego kościoła i umieszczono go również w głównym ołtarzu. W uroczystość Wniebowzięcia Najśw. Maryi Panny 1817 r. duchowieństwo dekanatu żywieckiego włożyło korony na obraz Matki Bożej Rychwałdzkiej. W pierwszej połowie XX w. przeprowadzono gruntowną odnowę świątyni, a w roku 1930 Paweł Palka z Łukowa na Podlasiu, wykonał istniejącą do dziś polichromię. 3 lipca 1946 r. kardynał Stefan Adam Sapieha powierzył parafię rychwałdzką Zakonowi Franciszkanów. 11 lutego 1947 r. w Rychwałdzie został erygowany klasztor

Długotrwały kult Matki Bożej Rychwałdzkiej został uwieńczony 18 lipca 1965 r., gdy Prymas Polski kard. Stefan Wyszyński i arcybiskup krakowski kard. Karol Wojtyła ukoronowali obraz Matki Bożej koronami papieskimi. W połowie lat 70. Zapoczątkowano odprawianie nabożeństw fatimskich. Po koniec lat siedemdziesiątych rozpoczęto odnawianie ścian z zewnątrz kościoła i budowę odwodnienia. W latach 80. dokończono tę pracę, i pokryto hełmy wieżowe blachą miedzianą. W połowie lat 80. od parafii rychwałdzkiej odłączono Pewel Ślemieńską i utworzono w niej samodzielną parafię. Odłączono również cześć Rychwałdku i przyłączono do nowo erygowanej parafii w Pewli Małej. W latach 90. uporządkowano plac kościelny i założono na nim oświetlenie elektryczne. 14 marca 1993 r. założono w kościele nowe, olejowe ogrzewanie. W drugiej połowie lat 90. sprawiono nowe, większe od dotychczasowych stacje Drogi Krzyżowej w kościele. 1 grudnia 1993 r. między biskupem Tadeuszem Rakoczym a prowincjałem o. Zdzisławem Gogolą została podpisana umowa o przekazaniu parafii św. Mikołaja w Rychwałdzie krakowskiej prowincji franciszkanów na okres 99 lat.

15 sierpnia 1995 r. poświęcono kamień węgielny budowanego domu rekolekcyjnego. W 2000 współbracia rychwałdzcy przenieśli się na i rok do domu rekolekcyjnego, a w tym czasie wykonano generalny remont klasztoru.

W tym też roku dom rekolekcyjny został przekazany pod zarząd Kurii Prowincjalnej. Zamieszkali w nim bracia z grupy rekolekcyjno-misyjnej. Początkowo nosił on nazwę Franciszkański Dom Rekolekcyjny „Quo vadis”. Obecnie nazywa się Franciszkański Dom Formacyjno-Edukacyjny.

W tym samym czasie kościół pokryto blachą miedzianą. W latach 2000-2004 dokonano odnowienia elewacji Kościoła, odnowienia polichromii wewnątrz świątyni, odnowienia ołtarza głównego i ołtarzy bocznych, odnowienia zabytkowych feretronów, odnowienia muru kościelnego i kaplic znajdujących się w murze: Matki Bożej Fatimskiej i Ciemnicy.

W latach 2004-2012 wykonano w kościele ogrzewanie podłogowe, wymieniono ławki na nowe, odrestaurowano ołtarze boczne, zakupiono nowe wiedeńskie żyrandole oraz umeblowano zakrystię.

W 2012 r. rozpoczęto prace nad kamiennymi stacjami drogi krzyżowej w murze przykościelnym, które zakończono w 2014 r. Stacje projektowała mgr Dorota Walijewska, a wykonał je jej mąż Andrzej. W 2014 w związku ze zbliżającym się jubileuszem 50-lecia koronacji cudownego wizerunku Maryi papieskimi koronami podjęto szereg prac renowacyjnych w sanktuarium. Wyremontowano organy, zamontowano sześć nowych lamp wiecznych, wymieniono blachę na hełmach wież kościoła, zrobiono nowe gabloty wotywne. Pracownia złotnicza Drapikowski Studio z Gdańska wykonała dla wizerunku Maryi „suknię wdzięczności” z ofiar wiernych i darczyńców oraz odnowiła korony i tabernakulum. Odrestaurowano również elewację zewnętrzną kościoła oraz poddano kompleksowej konserwacji cudami słynący obraz Matki Boskiej, czego podjęła się pracownia Marcin Chmielewski Modulus w Krakowie. Z tej pracowni wyszła też nowa kopia cudownego obrazu. 19 lipca 2015 pod przewodnictwem metropolity krakowskiego kard. Stanisława Dziwisza oraz Prymasa Polski abpa Wojciecha Polaka, w obecności prezydenta-elekta Rzeczypospolitej Polskiej Andrzeja Dudy obchodzono uroczyście złoty jubileusz koronacji łaskami słynący obraz Matki Bożej Rychwałdzkiej.

23 lipca 2017 roku podczas mszy św. dziękczynnej celebrowanej przez Prefekta Kongregacji Kultu Bożego i Dyscypliny Sakramentów kard. Roberta Saraha ogłoszono kościół pw. św. Mikołaja w Rychwałdzie Bazyliką Mniejszą.