A igreja de San Paolo alle Tre Fontane foi construída no século V no local onde, segundo a tradição, o próprio São Paulo foi martirizado por decapitação. No local lê-se uma placa: "S.PAULI APOSTOLI MARTYRII LOCUS UBI TRES FONTES MIRABILITER ERUPERUNT", ou seja: "lugar do martírio de São Paulo Apóstolo onde brotaram milagrosamente três fontes".
A mesma tradição sublinha que a cabeça do apóstolo, depois de cortada, bateu três vezes no chão antes de parar. Desses três pontos no solo, portanto, brotavam três fontes de água: a primeira quente, a segunda quente, a terceira fria. Assim, três bancas de jornais foram erguidas em memória do milagre ocorrido. Durante muitos séculos essa água foi distribuída aos fiéis por ser considerada milagrosa para a cura de doenças, mas a partir de 1950, devido à poluição, o fluxo foi fechado.
A igreja que pode ser vista hoje foi construída pelo arquiteto Giacomo Della Porta em 1599, encomendado pelo cardeal Pietro Aldobrandini.