Parafia nowosądecka swoje początki wiąże z lokacją miasta, która miała miejsce 8 listopada 1292 r. Miasto zostało założone na terenie wsi Kamienica, w której granicach już wtedy znajdowały się dwa kościoły: pierwszy pod wezwaniem św. Wojciecha, z istniejącą od XII wieku parafią, oraz drugi filialny, pod wezwaniem św. Małgorzaty.

 W momencie założenia miasta ówczesny kościół parafialny św. Wojciecha znalazł się poza granicami nowego miasta. Natomiast w jego granicach, a z czasem także w obrębie murów miejskich znalazł się kościół filialny św. Małgorzaty.Czas pracował na korzyść kościoła filialnego, który znajdując się w obrębie murów miejskich, blisko ratusza miał coraz większe szanse stać się "głównym" kościołem miasta. W 1325 roku wymieniono parafię Nowy Sącz wśród parafii należących do dekanatu sądeckiego, co suponuje, że już wtedy istniał w mieście kościół parafialny. Natomiast pieczęć dokumentu z 1343 roku przedstawia postać św. Małgorzaty na tronie, z koroną na głowie i włosami, których pukle rozchodzą się jak promienie, trzymającą w prawej ręce krzyż z proporcem, zaś w lewej model kościoła o jednej wieży, z ptakiem na dachu, Wydaje się to mieć związek z podniesieniem kościoła miejskiego do rangi kościoła parafialnego. Należy zauważyć, iż chociaż sama postać św. Małgorzaty była już umieszczana w pieczęciach dokumentów z 1306 i 1317 r., to jednak motyw kościoła pojawia się dopiero w roku 1343. Logicznym uzasadnieniem dla takiej treści pieczęci mogło być erygowanie nowej parafii przy dotychczasowym kościele filialnym św. Małgorzaty . Skoro bowiem miasto umieszczało w swej pieczęci świątynię, to nie była to z pewnością świątynia podrzędna, lecz kościół najznamienitszy, a takim był w przypadku Nowego Sącza kościół parafialny.
W miarę upływu czasu źródła podają coraz więcej informacji na temat kościoła parafialnego św. Małgorzaty w Nowym Sączu. Kardynał Zbigniew Oleśnicki w akcie z roku 1448 erygującym kolegiatę sądecką stwierdza, że podnosi do tej godności kościół funkcjonujący dotychczas jako parafialny, i że jest to kościół pod wezwaniem św. Małgorzaty, podlegający prawu patronatu i prezenty biskupów krakowskich. Świątynia ta była otaczana szczególną czcią i troskliwością mieszczan, przez co zjednała sobie nie tylko kard. Zbigniewa Oleśnickiego, ale i rajców miejskich. W taki sposób z kościoła filialnego, w okresie lokacji miasta, kościół pod wezwaniem św. Małgorzaty stał się przed rokiem 1325 niezależnym kościołem parafialnym, aby w XV wieku zostać wyniesionym do rangi kolegiaty.

Po wyniesieniu kościoła św. Małgorzaty do godności kolegiaty, kard. Oleśnicki uposażył kanoników bogatymi prebendami i innymi dochodami, a także zakupił im na mieszkania "stary ratusz", znajdujący obok kościoła. W skład kolegiaty wchodzili 4 prałaci: przełożony, czyli proboszcz, archidiakon, dziekan i kustosz, a także 4 kanonicy, jako członkowie kapituły tego kościoła. Tym samym dekretem, którym mianował kolegiatę, kard. Oleśnicki powołał do życia kolegium niższe tj. kapitułę mniejszą złożoną z ośmiu wikarych, a ich charakter prawny określił formułą vicarii perpetui.
W tym czasie rządom archidiakona nowosądeckiego podlegały następujące dekanaty: sądecki, biecki, bobowski, nowotarski, jasielski i pilźnieński. W wieku XVI i XVII do archidiakonatu tego należały też dekanaty: mielecki, ropczycki, strzyżowski, żmigrocki i spiski. W okresie reformacji, kiedy luteranizm i arianizm rozgościł się na ziemi sądeckiej zaczął stygnąć duch pierwotnej gorliwości wśród duchowieństwa sądeckiego. Pragnąc zaradzić dalszemu pogarszaniu się sytuacji kardynał książę Jerzy Radziwiłł zreformował kolegiatę w 1597 r. i nadał jej nowe obostrzone ustawy. Reformę uzupełnił w 1609 roku biskup Piotr Tylicki przez swego delegata, ks. Jana Januszowskiego, archidiakona sądeckiego. 13 marca 1786 r. papież Pius VI bullą "In suprema" utworzył z galicyjskiej części diecezji krakowskiej nową diecezję - tarnowską. W granicach nowopowstałej diecezji znalazł się Nowy Sącz. Taki stan utrzymywał się do czasu faktycznej kasaty tej diecezji w roku 1807, kiedy to konsystorz krakowski ogłosił dziekanowi w Nowym Sączu (10.12.1807 r.), że od tego czasu będzie należał do diecezji krakowskiej. W okresie kiedy jeszcze istniała diecezja tarnowska, została zniesiona w 1791 r. przez Franciszka Józefa II kolegiata sądecka, licząca w 1770 roku 7 dekanatów, 2 oficjały i 134 parafie i filie. Jednak faktycznym kresem kapituły było zagrabienie jej uposażenia na rzecz Funduszu religijnego i dekret z 26 maja 1786 r. zmieniający kapitułę kolegiacką na beneficjum proboszczowskie .

Po 343 latach kapituła sądecka przestała istnieć. Jednakże odegrała ona dużą rolę w życiu religijnym miasta i Sądecczyzny. Już wcześniej Franciszek Józef chciał doprowadzić do parcelacji parafii sądeckiej, jednak to mu się nie udało. Do sprawy tej powracano jeszcze w latach 1819 i 1823 ale i tym razem nic z tego nie wyszło, ze względu na brak dotacji nowych parafii. W okresie tym parafia liczyła ponad 8 tys. wiernych. Jak podaje w relacji z dnia 14 kwietnia 1846 r. ks. B. Janczy: "Parafianie sądeccy wiernie stali przy księżach w czasie wypadków rabacji. Kościół od nikogo nic nie ucierpiał".
Dnia 18 sierpnia 1855 r. Austria zawarła konkordat ze Stolicą Apostolską, który przyznawał Kościołowi katolickiemu szerokie wolności w zakresie działalności pastoralnej. Taka sytuacja wpłynęła na rozwój i pogłębienie życia religijnego w całej Galicji, a co za tym idzie także i w Nowym Sączu. Po wcześniej wspomnianej kasacie kolegiaty patronat nad kościołem św. Małgorzaty i parafią objął cesarz i on miał prawo do prezenty na urząd proboszcza.

W okresie tym byli nimi:
ks. Jakub Pstruszyński (1789-1800)
ks. Bartłomiej Janczy (1801-1852)
ks. Jan Machaczek (1853-1882)
ks. Wojciech Kowalik (1883-1887)
ks. Alojzy Góralik (1888-1926)
Przy parafii działały wtedy liczne bractwa i organizacje kościelne takie jak: Arcybractwo różańca św. i różaniec żywy, Apostolstwo modlitwy i Bractwo Najświętszego Serca Jezusowego, Arcybractwo wieczystej adoracji, Bractwo szkaplerzne i Bractwo Przemienienia Pańskiego. Przy parafii istniała także Katolicka Tania Kuchnia, która działała jeszcze po II wojnie światowej.
Narastająca liczba wiernych (w 1950 roku 24.986 katolików) sprawiła, że parafia św. Małgorzaty stała się najliczniejszą parafią w diecezji tarnowskiej. Rozległy obszar parafii obejmował nadal 26 wsi. Taki stan rzeczy domagał się podziału parafii, którego podjął się po II wojnie światowej bp Jan Stepa . W ciągu 44 lat na terenie parafii św. Małgorzaty w Nowym Sączu powstało 10 nowych parafii, a liczba księży pracujących w duszpasterstwie parafialnym wzrosła z 15 (1937) do 54 (1987).

W okresie tym proboszczami parafii św. Małgorzaty byli:
ks. infułat Roman Mazur (1926-1948)
ks. infułat Władysław Lesiak (1949-1977)
ks. prałat dr Stanisław Lisowski (1977-2000)

ks. prałat dr Waldemar Durda (2000 - 2007)
ks. prałat dr Andrzej Jeż (2007 - 2009)

ks. prałat dr Jan Piotrowski (2009 - 2014)

obecnie proboszczem parafii od 2014 r. jest ks. prałat dr Jerzy Jurkiewicz

Na prośbę bpa tarnowskiego Józefa Życińskiego, przedstawioną na piśmie z dnia 4 marca 1991 roku i wyrażającą pragnienie duchowieństwa oraz wiernych, papież Jan Paweł II nadał kościołowi parafialnemu św. Małgorzaty w Nowym Sączu tytuł Bazyliki Mniejszej. Sama uroczystość odbyła się w dniu 14 czerwca 1992 r. na placu Kolegiackim. Uroczystości przewodniczył ks. bp Józef Życiński, biskupi pomocniczy Józef Gucwa i Piotr Bednarczyk, a także licznie zgromadzeni przedstawiciele kościelni i państwowi. O podniesieniu kościoła do tej godności zadecydowały walory artystyczne, historyczne i kultyczne związane z kościołem św. Małgorzaty.
Ostatnim ważnym wydarzeniem w życiu parafii było reerygowanie kapituły kolegiackiej przy kościele farnym, która została zniesiona przez Józefa II w 1791 roku. Reerekcji kapituły kolegiackiej św. Małgorzaty dokonał ks. bp Józef Życiński w dniu 29 grudnia 1996 r.