Jeho výstavba teda vlastne predchádzala vzniku mesta. Prievidza sa totiž vyvinula z osady, ktorá sa v dávnych časoch sformovala v okolí tohto kostola. Podobne ako dnes i v minulosti ho obklopoval cintorín. Existenciu hradu potvrdzuje aj listina Ladislava V. z roku 1276. Po zániku hradu v roku 1321 existoval pri kostole benediktínsky kláštor, založený palatínom Leustachom z Jelšavy. Opustený kláštor a kostol s opevnením v 15. storočí prebudovali karmelitáni, ktorých povolal do Prievidze Leustachov syn Juraj. Ti do mesta a do mariánskeho kostola prichádzajú už v roku 1383. Ich konvent bol zasvätený Svätému krížu.
Za počiatok pútnickej tradície môžeme považovať rok 1430, kedy provinciál karmelitánskeho rádu priniesol do Prievidze pápežskú odpustkovú listinu pre návštevníkov kostola pri kláštore Svätého kríža. K milostivej soche Panny Márie z konca 15. storočia (dnes sa nachádza uprostred hlavného oltára z roku 1721) sa veriaci obracali s prosbami a modlitbami. Hlavný význam karmelitánov pre Prievidzu bol v ich školskom pôsobení. Vyučovanie bolo na úrovni stredných škôl. Karmelitáni kostol úplne prestavali v gotickom slohu. Budova kláštora (spomínaná r. 1496) nadväzovala na kostol od severnej strany. Svedčia o tom dodnes zvnútra viditeľné zamurované dvere na severnej strane veže. Ďalšou doteraz existujúcou pamiatkou na stavebné úsilie karmelitánov z konca 15. storočia je murovaná ohrada zosilnená pôvodne piatimi baštami, tvoriacimi opevnenie. Bašty boli neskoršie prestavané na kaplnky. Kostol bol ďalej upravovaný v rokoch 1682,1805, 1978-1992.
Karmelitáni, ktorí sa doteraz hlásia k heslu Carmel totus marianus (Karmel je celý mariánsky) boli veľmi horlivými prvými šíriteľmi pútnickej tradície v Prievidzi. Dnešný človek môže pohodlne žiť bez toho, aby sa staral o patróna svojej spoločenskej skupiny. Ale stredovekému človeku bolo nemožné zúčastňovať sa na živote skupiny a neuctievať pritom jej patróna. Podobne karmelitáni vedeli, že sú zasvätení Panne Márii, svojej patrónke a patrónke ich materského kostola na hore Karmel v Izraeli. Preto s rastúcim počtom karmelitánskych chrámov v Európe sa postupne vyvinul zvyk zasväcovať ich Panne Márii a tak upevňovať svoje zasvätenie a povolanie ako aj šíriť úctu k Presvätej Bohorodičke. O čom svedčia aj zakladacie listiny mnohých stredovekých karmelitánskych kostolov, kde sa uvádza vôľa karmelitánov, aby zriadením ich kostolov a kláštorov rástla mariánska úcta a zbožnosť ľudu. John Horneby z roku 1374 vyhlasuje: „Každé karmelitánske miesto s príslušným kostolom bolo zasvätené ku cti Panny Márie“.
Avšak kvôli riziku šíriacej sa reformácie karmelitáni mesto opustili. Kláštor zanikol v r. 1565. No pútnictvo celkom nezaniklo ani počas pôsobenia reformácie. Po vypovedaní evanjelikov z mesta a opätovnom prevzatí oboch kostolov katolíkmi v auguste 1660 bola mariánska púť slávnostne ustanovená na 15. augusta. Neskôr na túto tradíciu nadviazali piaristi (od roku 1666). Pútnická tradícia na tomto mieste pokračuje dodnes. Dúfajme, že miestni pastieri budú aj naďalej prostredníctvom stáročnej tradície oživovať vieru ľudu a ich úctu k tej, ktorá je našou Matkou, dokonalým vzorom svätosti a vernou sprievodkyňou k vrcholu dokonalosti - k Ježišovi Kristovi, nášmu Pánovi.