Lige siden året 130 lå der på det sted, hvor kirken Santi Giovanni e Paolo nu ligger på Monte Celio, et almindeligt beboelseshus i flere etager med hovedingang fra vejen, der flankerede det store Claudius-Tempel, Claudianum, som Agrippina lod opføre i år 54 efter Kristus.

Ved siden af lå tilsyneladende også et andet hus, hvori der var nogle butikker. Disse blev siden tilmuret og inddraget i husene ovenover og sidst i det 3.århundrede ændredes disses udseende.

Det var således i løbet af det 2.århundrede, at Monte Celio blev bebygget med rige romeres privathuse og her boede romere, der stadig fulgte den gamle religion, men i det 3.århundrede ejedes huset af en kristen romer, som siden overtog huset ved siden af kirken og ombyggede de 2 huse til ét kristent bedehus.

Her boede ifølge legenden de 2 kristne romerske officerer Giovanni og Paolo, som døde som martyrer under Kejser Julian i år 362, og her fandt deres venner Crispo, Crispiniano og Benedetta deres lig, og her opstod dyrkelsen af de 2 martyrer.

Også den kristne senator Byzans (Bizante) ejede et hus her på Celio og sammen med sin søn Pammachius (Pammachio) grundlagde han "Titulus Pammachii", det kristne bedehus, hvori martyrerne Giovanni og Paolo blev dyrket, og her blev der bygget en kirke for dem omkring år 398.

Disse huse er nu blevet udgravet og kan beses fra kirken Santi Giovanni e Paolo, hvor man fra højre sideskib ad en trappe kommer ned til resterne af 3-4 forskellige bygninger: 1-2 romerske beboelseshuse i 2 etager, et kristent bedehus og et lille middelalder-kapel, over 20 rum ialt.

De rum, der viser den tidlige kristendom her på stedet ligger midt under den nuværende kirke. Det er først og fremmest et lille rum med røde vægmalerier på hvid bund, her ses en "Orante", en bedende person med udbredte arme, det var måden at bede på (orare) i oldkristen tid og rummet kaldes netop "Aula detta della orante". Loftet er bemalet med "Læsende Apostle" og dyr og planter.

Lidt højere oppe og inde mod kirkens midte ligger nogle rum med tøndehvælvet loft, som muligvis har været et tidligt kristent bedehus, her findes rester af fresker fra det 3.århundredes udsmykning.

Længere nede i kirken mod den nuværende Piazza dei Santi Giovanni e Paolo ligger så de 2 martyrers grav, som kunne betragtes fra nogle tilliggende rum, som er blevet bemalet med fresker i det 4.århundrede fremstillende martyrerne og deres venner, Benedetta, Crispo og Crispiano, som finder dem myrdet og derpå selv lider martyrdøden.