Ifølge legenden var Santi Giovanni og Paolo (Johannes og Paulus) 2 tidligt kristne martyrer, der levede i det 4.århundrede efter Kristus. De var soldater og blev sendt i krig under generalen Gallicanus. Da hæren var ved at lide nederlag, lærte de 2 kristne officerer generalen at bede om Guds hjælp og de vandt derved slaget.

Kejser Julian (361-363), der modarbejdede kristendommen, ønskede at svække de 2 officerers ry og beskyldte dem for ikke at følge Jesus' bud, da de ikke levede i fattigdom. De svarede ham, at hvad de ejede også tilhørte de fattige, men Julian forsøgte nu at overtale dem til at vende sig fra Kristendommen og ofre til de romerske guder. Da de nægtede, fik de en frist på 10 dage og da de stadig ikke ville afsige deres tro, lod han dem dræbe i deres eget hjem på Celio-højen i Rom.

Da man i nogle dage ikke havde hørt og set dem, blev deres 3 venner Crispo, Crispiniano og Benedetta urolige og gik over til deres hus ved Clivus Scauri, hvor de fandt vennernes lig, sørgede for deres begravelse og fortalte historien videre, således at stedet blev centrum for dyrkelsen af de 2 martyrer og senatorerne Byzans og Pammachius, der var fader og søn, lod rejse en kirke (Basilica Pammachiana) over det hus, hvor de 2 officerer havde levet og nu lå begravet under den nye kirkes apsis. Denne kirke blev ødelagt under barbarinvasionen i 410 og i årene efter genopbygget og indviet til Santi Giovanni e Paolo.

En anden version af legenden fortæller, at de var officerer under den kristne Kejser Constantin, men trak sig tilbage fra tjeneste, da Julian den Frafaldne kom til magten, hvorved de pådrog sig hans vrede, så han natten mellem den 26. og 27. juni i år 361 lod dem dræbe af Terenziano, som senere fortrød og gik over til kristendommen.