To jeden z najstarszych budynków Sandomierza. Pochodzi z 1226 roku. Wówczas zbudowano go z drewna, na polecenie Iwona Odrowąża ? biskupa krakowskiego.
Po pożarze na jego miejscu wzniesiono jednonawową gotycką świątynię z trójbocznie zamkniętym prezbiterium.
W okresie baroku kościół został ponownie przebudowany. Pojawiły się sztukaterie sklepień oraz nowy ołtarz, stalle w prezbiterium, chór organowy, a także ambona. Wnętrze zaskakuje licznymi polichromiami.
Ciekawym architektonicznym dodatkiem do kościoła Nawrócenia św. Pawła jest mur z barokową dzwonnicą oraz plebania w stylu drewnianego, staropolskiego dworu.
Świątynia leży tuż obok wąwozu świętej Królowej Jadwigi i w pobliżu kościoła świętego Jakuba.