Najstarsza wzmianka o Tarnowie jako wsi należącej do opactwa Benedyktynów w Tyńcu pochodzi z roku 1105. W nieokreślonym bliżej czasie Tarnów stał się własnością rodu Łabędziów a w 1327 drogą zamiany na wieś Dębno nabył wieś Tarnów Wielki Spycymir z Melsztyna, wojewoda krakowski. Dnia 7 marca 1330 r. dokumentem wydanym w Krakowie, król Władysław Łokietek lokował na terenie wsi Tarnów Wielki i Tarnów Mały miasto Tarnów na zasadach prawa magdeburskiego, jako prywatne miasto Leliwitów. W XIV w Spycymir wzniósł dwa zamki w Tarnowie i Melsztynie, w których osadził synów - Rafała w Tarnowie i Jana zwanego Spytkiem w Melsztynie. W ten sposób stał się protoplastą dwóch rodów możnowładczych Tarnowskich i Melsztyńskich. W wieku XV ród Tarnowskich podzielił się na linię tarnowską, która wygasła na Janie Krzysztofie w 1567 r., oraz linię rzochowską, która trwa do dzisiaj. Tarnów po śmierci Jana Krzysztofa Tarnowskiego stał się własnością Ostrogskich, następnie Zasławskich, Lubomirskich, Zamoyskich, Sanguszków a od 1787 stał się własnością rządu. 

Powstanie parafii w Tarnowie wiąże się z lokacją miasta. Wobec braku dokumentów erygujących parafię, przyjmuje się, że kościół parafialny na terenie miasta został wzniesiony w pierwszej połowie XIV w., taka bowiem była ówczesna praktyka kościelna, że w obrębie murów miejskich erygowano parafię i budowano kościół zapewniając opiekę duszpasterską mieszkańcom miasta. Kościół wzniesiony w Tarnowie od początku nosił wezwanie Narodzenia Najświętszej Maryi Panny. Był na tyle okazały, że w 1392 r. odbyła się w nim konsekracja biskupia Jakuba Strepy, na biskupa halickiego, a w 1400 r. biskup krakowski Piotr Wysz wyniósł go do godności kolegiaty i powołał przy nim do istnienia Kapitułę Kolegiacką, która w chwili erygowania liczyła 3 prałatury i 2 kanonie. Od tego czasu Kolegiata Tarnowska była kościołem parafialnym dla miasta Tarnowai okolicznych wsi, a istniejące ośrodki duszpasterskie św. Marcina w Zawadzie i w zamku Tarnowskich zostały zniesione, a ich uposażenie stało się uposażeniem Prałatów i Kanoników Kapituły Kolegiackiej. W roku 1786, w związku z utworzeniem przez papieża Piusa VI Diecezji Tarnowskiej, świątynia pod wezwaniem Narodzenia NMP w Tarnowie otrzymała tytuł Katedry. Papież Paweł VI listem Apostolskim "Cum beatissima" z dnia 14 kwietnia 1972 r. nadał katedrze tarnowskiej tytuł Bazyliki Mniejszej, ze względu na jej wyjątkowe znaczenie dla kultu Bożego i chrześcijańskiej kultury..