Reaproveitando os vestígios de antigas construções da época imperial, esta igreja foi erguida no século VII tomando o nome da rua em que se situava, que foi o primeiro trecho urbano da Via Flaminia.
Grandes reformas realizadas no Ano Santo de 1650 transformaram completamente a igreja, dando-lhe o aspecto barroco atual.
A tradição indica precisamente este local como aquele onde São Paulo foi mantido prisioneiro, de fato ainda hoje na seção subterrânea existe uma coluna à qual ele teria sido amarrado e um poço de onde teria jorrado uma fonte divina seguindo as orações do Santo.