La chiesa di San Paolo, all'interno del complesso abbaziale delle Tre Fontane, è la più antica delle tre chiese costruite all'interno di questa conosciutissima abbazia romana.

La chiesa sorge sul luogo, anticamente chiamato ad aquas salvias, dove, secondo la tradizione, san Paolo subì il martirio con la decapitazione: la leggenda racconta che la sua testa, una volta tagliata, abbia rimbalzato tre volte sul terreno, facendo scaturire ad ogni balzo una sorgente d'acqua, una calda, una tiepida ed una fredda; da qui il nome del toponimo delle tre fontane. In seguito si aggiunse la tradizione secondo la quale la decapitazione di san Paolo fosse avvenuta lungo la via Ostiense, nel luogo dove fu poi sepolto e fu costruita in epoca costantiniana la basilica di San Paolo fuori le mura. Questa prima chiesa fu completamente rifatta nel XVI secolo ad opera di Giacomo della Porta, tra il 1599 ed il 1601, per volere del cardinale Pietro Aldobrandini.

La chiesa fu restaurata sotto Pio IX nel 1867. In questa occasione un ampio mosaico policromo del II secolo con le immagini delle Quattro stagioni, proveniente dal mitreo imperiale di Ostia, fu installato nella navata centrale.

Sull'altare della cappella di sinistra era installata la Crocifissione di Guido Reni, trasferita a Parigi dai francesi nel 1797. Quando fu recuperata, venne allocata alla Pinacoteca Vaticana: la pala attualmente in loco è una copia. Sull'altare della cappella di destra è collocata una decollazione di san Paolo di Bartolomeo Passerotti.