Kościół pod wezwaniem św. Pawła Apostoła jest jednąz najstarszych świątyń Sandomierza. Pierwotny, drewniany, ufundowany został przez krakowskiego biskupa Iwona Odrowąża na dawnym wzgórzu staromiejskim w 1226r. wtedy też została ustanowiona
parafia. Obecny kościół murowany wybudowany został w latach 1426 - 1434. W XVII w. pierwotną jednoprzęsłową prawie kwadratową nawę powiększono o jedno przęsło i nakryto sklepieniem kolebkowym zdobionym geometryczną dekoracją stiukową w typie renesansu kalisko - lubelskiego. Od 1650 r kościół św. Pawła przestał być parafią, zdany na wikariuszy
kolegiaty podupadł, podźwignięty po przywróceniu parafii w 1688 r., dopiero przez ks. Jakuba Orzechowskiego.
Obecny kościół św. Pawła wzniesiono jako murowany w początku XV w. Z tego czasu zachowała się fragmentarycznie na ścianach prezbiterium polichromia gotycka w postaci inskrypcji mówiącej o poświęceniu przez biskupa Zbigniewa Oleśnickiego nowo
wzniesionego kościoła. Polichromia ta po odsłonięciu została zabezpieczona i pozostaje niedostępna za stallami. Jej fotokopia wisi na ścianie bliżej chóru muzycznego.