Kościół ma piękną historię. W 1395 roku wzniesiono go z fundacji świętej Jadwigi Andegaweńskiej i Władysława II Jagiełły, ale legenda mówi, że jego budowę w XI wieku rozpoczął Władysław I Herman. W 1397 roku świątynię przejęli Karmelici Trzewiczkowi. W XVI wieku gotycki kościół został uszkodzony w czasie oblężenia miasta. Choć został później odbudowany, nie ominęły go kolejne zniszczenia w czasie najazdu szwedzkiego. Odnowiono go w XVII wieku i przetrwał do dziś. Elewacja bazyliki wzorowana jest na fasadzie rzymskiego kościoła Il Gesù. Przy kościele znajduje się Golgota z rzeźbami z XVIII wieku. Uwagę zwraca barokowy ołtarz główny z XVIII wieku z dekoracją snycerską oraz stalle z XVII–XVIII wieku. Na ścianie świątyni od ulicy Garbarskiej, znajduje się cios kamienny z odciskiem tak zwanej stopki królowej Jadwigi. Legenda głosi, że królowa, która często nawiedzała świątynie w trakcie budowy, wzruszona niedolą jednego z budowlańców, postawiła stopę na kamieniu i odpięła z bucika złotą klamrę. Robotnicy ze zdziwieniem zauważyli, że w kamieniu został odciśnięty ślad jej stopy. Barokowy klasztor z XVII wieku nadbudowano w XX wieku o dwa piętra. W krużgankach widać freski z XVIII wieku przedstawiające dzieje kościoła i cudownego obrazu. Przylegającą do kościoła kaplicę Matki Boskiej Piaskowej, projektu Giovanniego Trevano, kryje kopuła z latarnią z posągiem Madonny z XVII wieku. Wizerunek Matki Boskiej Piaskowej zwanej Panią Krakowa, w XV wieku namalował nieznany zakonnik, który według legendy przerwał rozpoczęte dzieło, a obraz jednak został cudownie ukończony. Obraz nie spłonął w czasie pożaru kościoła w 1655 roku, przed nim modlił się Jan III Sobieski w 1683 roku przed wyprawą pod Wiedeń, a w dwusetną rocznicę zwycięstwa pod Wiedniem nałożono na niego korony projektu Jana Matejki. Główna uroczystość ku czci Maryi przypada tu 16 lipca w święto Matki Bożej Szkaplerznej.

Tu przed wizerunkiem Madonny wierni modlą się od lat. Obraz, który mieści się w sanktuarium poświęconym w 1966 roku przez arcybiskupa Karola Wojtyłę, swój kult datuje już od XVII wieku.

Pierwszy drewniany kościół świętych Mikołaja Biskupa i Marii Magdaleny powstał z fundacji Kazimierza II Sprawiedliwego w XI–XII wieku, a nawet w X wieku, i jest jednym z najcenniejszych romańskich zabytków w kraju oraz najstarszym obiektem sakralnym polskich Karpat. Odkryto w nim rzadkie polichromie z XII stulecia. W XVII wieku w miejsce zniszczonego kościoła wzniesiono nowy z zachowaniem romańskiej wschodniej części zbudowanej z kamiennych ciosów. W kościele w bocznym ołtarzu umieszczono słynący łaskami i otaczany kultem obraz Macierzyństwa Najświętszej Maryi Panny. Dziś obraz Matki Bożej Dziekanowskiej znajduje się w sąsiednim dużym kościele Macierzyństwa Najświętszej Marii Panny, zbudowanym w latach 1960–1966 na stromym wzgórzu nad Rabą. Kult obrazu Matki Bożej Dziekanowskiej rozpoczął się w XVII wieku. Jest to wizerunek namalowany na płótnie przez nieznanego artystę ze szkoły krakowskiej. Obraz w 1991 roku koronował Jan Paweł II. Główny odpust w sanktuarium przypada na Święto Macierzyństwa Najświętszej Marii Panny w pierwszą niedzielę po 11 października. Inne odpusty obchodzone są 22 lipca w święto świętej Marii Magdaleny i 6 grudnia w dzień świętego Mikołaja.