Wykorzystując pozostałości starożytnych budowli z czasów cesarstwa, kościół ten został wzniesiony w VII wieku, biorąc swoją nazwę od ulicy via Flaminia, przy której stał, a która była pierwszym miejskim odcinkiem, dla pielgrzymów przybywających z północy Włoch do Rzymu.
Gruntowne remonty przeprowadzone w Roku Świętym 1650 całkowicie zmieniły wygląd kościoła, nadając mu obecny barokowy styl.
Tradycja głosi, że to właśnie w tym miejscu więziony był św. Paweł. Do dziś w części podziemnej znajduje się kolumna, do której był przywiązany, oraz studnia, z której wytrysnęło źródło wody po modlitwach świętego.