Jednym z istotniejszych elementów średniowiecznego zespołu osadniczego w początkach Sandomierza było wzgórze zwane świętojakubskim z kościołem p. w. św. Jakuba, przekazanym sprowadzonym doń w 1226 roku staraniem krakowskiego biskupa Iwona z rodu Odrowążów zakonnikom dominikańskim. Przekazanie istniejącej świątyni zdecydowało o konieczności powstania nowego kościoła parafialnego dla, zapewne dość licznej, grupy mieszkańców podgrodzia.

Fundatorem kościoła dla nowo utworzonej parafii miał być także biskup krakowski Iwo. Nowy kościół p. w. św. Pawła był niewątpliwie świątynią drewnianą, usytuowaną na wzgórzu, zwanym od jego wezwania świetopawelskim, zapewne mniej więcej w tym samym miejscu, gdzie stoi dzisiejszy kościół. Niestety, z powodu braku zachowanych źródeł i poważniejszych badań terenowych, nie są zbyt dobrze znane dalsze losy drewnianej świątyni. Nie można wykluczyć, że pierwotna świątynia, usytuowana na terenie osady pozbawionej urządzeń obronnych, została zniszczona i spalona w trakcie kolejnych najazdów mongolskich, ruskich i litewskich, choć podobnie przyjąć można, że tuż po nich podnosiła się ze zgliszcz i była odbudowywana, również jako budowla drewniana.

Doniosłe wydarzenia w historii kościoła św. Pawła miały miejsce dopiero u schyłku średniowiecza. Wiadomo bowiem, że w 1 poł. XV wieku, na miejscu starszego, drewnianego, powstała nowa, murowana świątynia. Dokonać tego miał kanonik i oficjał sandomierski a miejscowy proboszcz imieniem Grzegorz, o czym informuje Jan Długosz notując, że Gregorius ejus tunc plebanus, canonicus et officialis sandomiriensis, ecclesia lignea demolita, ipsam in latericiam fabricavit. Wspomniany Grzegorz występuje w źródłach jako proboszcz w 1426 roku, więc na pocz. 2 ćw. XV wieku należałoby datować powstanie murowanej świątyni. Dodatkowych informacji dostarczyła odkryta niedawno inskrypcja poświadczająca, że kościół był poświęcony przez Jarosława sufragana działającego w imieniu biskupa krakowskiego Zbigniewa. Wspomniany biskup to oczywiście urzędujący w latach 1423-55 Zbigniew z Oleśnicy, zaś sufraganem był niewątpliwie zmarły ok. 1445 roku dominikanin, przeor konwentu lubelskiego, Jarosław z Lublina, często zastępujący zapracowanego biskupa w czynnościach liturgicznych, w szczególności konsekracyjnych.

Poświęcenie nastąpiło więc w ciągu 2 ćw. XV wieku, zapewne wkrótce po wystawieniu kościoła.

Murowany kościół nie oparł się pożarowi w 1637 roku. Zniszczenia okazały się zapewne dość dotkliwe, a i może świątynia była już wówczas zbyt ciasną, gdyż w ramach odbudowy zdecydowano o powiększeniu kościoła poprzez wydłużenie nawy. Niezbędne prace rozpoczął i przeprowadził własnym kosztem kanonik sandomierski i proboszcz kościoła od 1631 roku, ks. Szymon Dzierżęga. Najprawdopodobniej zniszczeniu uległo również wyposażenie, wspaniale uzupełnione także staraniem proboszcza. Wiemy, że 13 lipca 1651 roku, jeszcze przed śmiercią ks. Dzierżęgi w następnym roku, dwa nowe ołtarze konsekrował biskup sufragan krakowski Wojciech Lipnicki.

Niestety, w wyniszczających latach potopu szwedzkiego, świątynia znowu doznała poważnych uszkodzeń. Szwedzi i wojska księcia siedmiogrodzkiego Jerzego II Rakoczego zrabowali wiele sprzętów kościelnych, a samą świątynię sprofanowali. Kościół jednakże niebawem naprawiono i zaopatrzono w niezbędne sprzęty, a biskup sufragan krakowski Wojciech Lipnicki poświęcił sprofanowane ołtarze. Kolejny sufragan krakowski, biskup Mikołaj Oborski, w 1660 roku dokonał ponownej konsekracji kościoła.

Niestety, kolejni wyznaczeni po 1650 roku do opieki nad kościołem wikariusze kolegiaty sandomierskiej niezbyt troszczyli się o kościół, nie dopełniali bieżących, koniecznych napraw i w efekcie braku dbałości, stan świątyni bardzo się pogorszył. Dach na kościele był bardzo zniszczony, ogrodzenie przykościelnego cmentarza zrujnowane a drewniana dzwonnica groziła zawaleniem. Zupełnie zapuszczone były nawet zabudowania plebańskie i szkolne. Szczęśliwie dla dalszych losów kościoła, w 1688 roku archidiakon sandomierski ks. Rafał Rościcki, jako opiekun kościoła, wyjednał dekret u Stolicy Apostolskiej, przywracający kościołowi św. Pawła funkcje parafialne. Kroniki kościelne przekazały informację, że, już jako proboszcz, ok. 1690 roku sprowadził z Wenecji piękny obraz przedstawiający Boże Narodzenie.

Jednakże ostateczny kształt i wystrój wnętrza kościół zawdzięcza kanonikowi Jakubowi Orzechowskiemu, proboszczowi parafii w latach 1706-24. Już w 1706 roku jego staraniem dano w kościele nową posadzkę z marmuru chęcińskiego i odmalowano obraz Nawrócenia św. Pawła z ołtarza głównego. Jego też kosztem w 1715 roku, pracujący nad swymi wielkimi obrazami w kolegiacie, malarz Karol de Prevot wykonał dwa obrazy, przedstawiające historie z życia św. Pawła Apostoła, patrona parafii. Potwierdzeniem są zapiski w kronice kościelnej informujące, że w 1715 r. P. Karolowi de Prewo za dwa Obrazy S. Pawła zł. 64. wypłacono. Były to zapewne obrazy przedstawiające „Cud ze żmiją na Malcie" i „Uzdrowienie chorego mężczyzny" z nastawy ołtarza głównego. Wiemy także, że wypłacono w 1719 r. P. Karolowi za trzy Obrazy Taler bit 6 ...40 zł, a były nimi zapewne trzy małe obrazki, w tym przedstawienie Głowy Chrystusa. Jeszcze raz płacono w 1724 roku za dwa Obrazy P. Karolowi Malarzowi... 83 zł 24 gr., przy czym ta zapłata mogła dotyczyć obrazów z zaginionego tryptyku ołtarza św. Barbary.

Ważnym wydarzeniem, także związanym z kanonikiem Jakubem Orzechowskim, było utworzenie pobożnego bractwa wiernych obojga pici, pod wezwaniem św. Barbary na cześć i chwałę Boga Wszechmogącego, dla zbawienia dusz, dla pomocy bliźnim ... którego to bractwa umiłowani synowie współbracia mają zwyczaj wykonywać bardzo liczne uczynki miłości i miłosierdzia, kultywującego więc potrzebę modlitwy oraz podejmowanie działań o charakterze dobroczynnym i apostolskim, zwłaszcza na rzecz ciężko chorych. Z zamiarem utworzeniem bractwa wiąże się też powstanie kaplicy p. w. św. Barbary i sprowadzenie relikwii świętej.

Bractwo zatwierdzone zostało bullą papieża Klemensa XI z 1718 roku, ogłoszoną przez biskupa sufragana przemyskiego Stanisława Józefa Hozjusza, z poleceniem nadania uroczystości inauguracji działalności bractwa niezwykle uroczystego charakteru. Zgodnie z tymi zaleceniami, w dzień św. Barbary 1719 roku zjechało do Sandomierza przeszło dziesięć tysięcy wiernych. Po skończonym nabożeństwie w kolegiacie, wielka procesja, mijając trzy bramy triumfalne, dotarła do kościoła św. Pawła, gdzie dokonano pierwszych zapisów do bractwa. Służyła temu specjalnie przygotowana, ozdobna „Księga Żywota Wszytkim Prawowiernym Żyć Wiecznie Pragniącym w Bractwie S. Barbary Panny y Męczenniczki Chrystusowey Patronki Umieraiących Otworzana w Kościele Farnym S. Pawła Apostoła na Starym Sandomierzu Roku Pańskiego 1719", która zachowała się do dnia dzisiejszego.

Nic więc dziwnego, że wizytujący kościół w 1727 roku, z upoważnienia biskupa krakowskiego Felicjana Konstantego Szaniawskiego, archidiakon sandomierski ks. Dominik Lochman zanotował nie tylko, że kościół bardzo starożytny, z cegły zmurowany, podobną mający zakrystję, po pożarze, (około 1640 r.) nie małym funduszem ks. Szymona Dzierżęgi, kan. Sand. proboszcza tej parafii wyrestaurowany, ale też podkreślił, że to właśnie ks. Jakub Orzechowski przyozdobił świątynię naczyniami srebrnemi do służby Bożej używanemi, oraz ołtarzami, malaturą i złoceniem, a do tego jeszcze kapliczkę świętej Barbary z fundamentu zbudował i uposażył, a dach jej pokrył białą blachą.

Następca ks. Orzechowskiego, ks. Marcin Jasiński, proboszcz w latach 1728-47, niemniej od poprzednika dbał o parafialną świątynię. Jego staraniem kościół pokryty został blachą miedzianą, a cmentarz przykościelny ogrodzony murem. Wnętrze kościoła w 1739 roku wzbogaciły ołtarze św. Barbary oraz śś. Kajetana i Jana Kantego, poświęcone w tym samym roku przez scholastyka sandomierskiego i biskupa inflanckiego, Wacława Hieronima Sierakowskiego.

Ukoronowaniem działalności proboszcza było wystawienie własnym kosztem w 1745 roku wspaniałej, murowanej dzwonnicy.

Lata względnego spokoju w dziejach parafii i kościoła przerwały działania zbrojne i niepokoje w pocz. XIX wieku. W czasach administrowania parafią przez byłego jezuitę i profesora fizyki w lwowskim kolegium, w latach 1800-23 proboszcza, ks. kan. Józefa Lisikiewicza, Sandomierz stał się widownią walk kampanii prowadzonej pod dowództwem ks. Józefa Poniatowskiego w 1809 roku, stanowiącej etap wojny Napoleona z Austrią. Szczególnie dotkliwie ucierpiały wówczas kościół św. Pawła i zabudowania plebańskie. Wspominając te wydarzenia, ks. Lisikiewicz zanotował w kronice parafialnej, że ten rok fatalnym stał się dla kościoła i pobudynków plebanii świętego Pawła, albowiem wyrobiona została fortyfikacja przez wojska austryjackie przy kościele..., zaś potem,... za nadejściem od Warszawy z Xięciem Ferdynandem wojska Austriackiego najtęższy atak do tej baterii przypuszczony podczas którego granaty okna od końca Kościoła mu bliższe churu iedno od Północy drugie od Południa z ramami kratą zruinowały przytym w blasze miedzianej ktyrą pobity Kościół wielu dziur Kulami Karabinowymi z wyednym mieyscu Kulą armatnią lub granatem zrobiły ... Pamiątką po tamtych, tragicznych wydarzeniach jest kilka kul i kartaczy, pozostawionych w murach kościoła.

Należy wyrazić uznanie dla ks. Listkiewicza, który stosunkowo bardzo szybko, bo do 1812 roku odbudował zniszczone zabudowania gospodarcze plebani i wyremontował uszkodzony działaniami wojennymi kościół. W kolejnych latach, staraniem administrującego parafią od 1862 roku proboszcza ks. Wawrzyńca Szubartowicza odnowiono i przyozdobiono kościół. Kolejni proboszczowie byli w znacznie lepszej sytuacji, gdyż prawie przez cały wiek kościół i parafia pozostawały we względnym spokoju.

Dopiero lata I wojny św. przyniosły kolejne cierpienia i zniszczenia. Zwłaszcza tragicznie zapisał się 1915 rok, kiedy to od 6 do 8 września toczyła się tu krwawa bitwa między wojskami rosyjskimi i austriackimi, tym bardziej bolesna, że po obu stronach walczyli Polacy. W czasie walk poległo kilkuset żołnierzy, których część pochowano na cmentarzu, a część we wspólnej mogile na polu plebańskim.

Sam kościół, który już przed I wojną św. należało poddać gruntownej odnowie, w czasie działań wojennych doznał kolejnych poważnych uszkodzeń. Blacha na dachu została zniszczona, a ściany i mury uszkodzone pociskami armatnimi.

Naprawa zniszczeń nie przyszła łatwo. Trudu podjął się proboszcz ks. Franciszek Rolecki, który w latach 1926-27 naprawił zaistniałe uszkodzenia i - znowu na pamiątkę - obok dawnych kul z 1809 roku umieścił parę szrapneli z 1914 roku.

Dziś kościół św. Pawła, staraniem i dbałością kolejnych proboszczów, należy do najwspanialszych w diecezji i stanowi nierozerwalną część krajobrazu pięknego i starożytnego Sandomierza.