Parafia powstała w 1226 r. z inicjatywy biskupa krakowskiego. W tym samym czasie sprowadził on do Sandomierza dominikanów, kształtując dwa ważne ośrodki życia religijnego: klasztor oraz parafię na wzgórzu świętopawelskim – przypomina proboszcz, ks. Krzysztof Rusiecki. – Wspólnota została przeniesiona z Kościoła św. Jakuba. Pierwsza świątynia była drewniana, a dawny Sandomierz rzemieślniczy skupiał się właśnie wokół Kościołów św. Pawła i św. Jakuba.

Do parafii należało wówczas jedenaście wiosek. Taki stan utrzymywał się aż do reorganizacji w latach 80. XX wieku. Dziś jest to już wspólnota typowo miejska, ale jej korzenie sięgają czasów, gdy religia, handel i rzemiosło splatały się w jedno.