Selama berabad-abad, Coelius Maior (Celio Maggiore) tetap menjadi bukit yang hampir sepenuhnya tidak berpenghuni. Kawanan ternak merumput di sini di antara kebun buah dan kebun anggur.
Di bukit kuno ini, di sebelah kiri Clivo di Scauro yang juga kuno, sebuah basilika dibangun di atas rumah saudara-saudara Yohanes dan Paulus, pejabat istana yang sangat berpengaruh, yang menjadi martir karena iman Kristen pada 26 Juni 362, pada masa pemerintahan Yulianus si Murtad (+ 363).
Wilayah ini unik dalam sejarah arkeologi Romawi. Di sini terdapat jejak-jejak pemujaan Kristen primitif bersama dengan sisa-sisa seni sebelumnya yang jelas.
Setelah pembunuhan saudara-saudara tersebut, martir Kristen lainnya---Crispo, Crispiniano, dan Benedetta---dikuburkan di sini.
Penghormatan kepada para martir suci di Celimontana mencapai puncaknya pada akhir abad ke-4 dengan pembangunan sebuah bangunan ad corpora oleh Senator Bizanzio.
Kemudian, putra Senator Pammachius (+ 410), seorang teman St. Hieronimus, mengubah bangunan tersebut menjadi bentuk sebuah Basilica magna et valde formosa (besar dan indah) seperti yang dinyatakan dalam Itinerary of Salisbury.
Basilika ini dijarah dan dihancurkan pada masa serangan Visigoth pada tahun 410, dan pada abad VI dan VII, basilika ini sering dikunjungi oleh banyak peziarah yang saleh. Basilika ini juga dihiasi dengan berbagai ornamen. Nama-nama martir militer ditempatkan dalam Kanon Misa Romawi.
Di Roma, terdapat dua gereja lain yang dinamai sesuai para martir Celimontana. Salah satunya berada di Bukit Janiculum. Yang lainnya, bersama dengan biara yang terhubung, dibangun oleh Santo Leo Agung sekitar tahun 440, di area yang saat ini ditempati oleh transept Saints Martinian dan Processo di Basilika Santo Petrus.
Dua imam, Proclinus dan Ursus, memegang gelar basilika ini selama masa kepausan Paus Inosensius I (+ 417).
Empat imam, dua dari gelar Bizanzio dan dua dari gelar Pammachius, hadir di Sinode Roma tahun 499.
Menurut katalog Peter Mallio, yang disusun pada masa kepausan Paus Alexander III (+ 1181), gelar tersebut pada waktu itu terhubung dengan basilika Saint Lawrence Outside the Walls, dan para imamnya bergantian merayakan Misa di sini. Gereja ini telah beberapa kali dipugar.
Paus Simachus pada abad ke-5 dan kemudian Leo III pernah menduduki basilika ini. Kultus para martir Celimontana menyebar ke seluruh Gereja. Seorang Lektor bernama Massimino, yang meninggal pada tahun 567 di usia 20 tahun, melayani di basilika ini. Selama berabad-abad, layanan liturgi disediakan oleh komunitas kecil kanon (atau biarawan) hingga tahun 1000. Setelah kerusakan yang disebabkan oleh orang Norman Robert Guiscard, pemugaran basilika dan biara diperintahkan oleh pemegang gelarnya, Kardinal Theobald, pada masa Paus Paschal II (+ 1118).
Selain kerusakan akibat waktu, beberapa gempa bumi juga menyebabkan kerusakan yang signifikan. Selain itu, portiko Ionik yang didukung oleh delapan tiang dengan ibu kota Ionik, yang berasal dari abad ke-12 (dibangun untuk menggantikan narthex lama), serta apsis diselesaikan oleh Kardinal Giovanni dei Conti di Sutri (1216) dan oleh Adrian IV. Menara lonceng dibangun pada tahun 1115.
Renovasi penting lainnya terjadi pada tahun 1718 (oleh arsitek Antonio Canevari dan Giovanni Andrea Garagni dari Piedmont), yang mengubah interior basilika ke bentuknya saat ini.
Renovasi ini dipesan oleh Kardinal Fabrizio Paolucci (+ 1719) dan sepenuhnya mengubah tampilan basilika Paleokristen yang sebelumnya "terbuka" dan sangat terang. Transformasi ini dimulai oleh Kardinal Philip Howard pada abad sebelumnya.
Interior basilika ini besar dan megah, dibagi menjadi tiga lorong oleh tiang dan pilar. Lantainya berornamen Cosmatesque. Beberapa meter dari pintu masuk, di lorong tengah, terdapat lempengan marmer yang menandai lokasi bawah tanah dari tempat kemartiran.
Relik para martir suci dimakamkan di bawah altar tinggi dalam sebuah urna dari pofiri.
Di lorong kanan, sebuah kapel mewah dibangun pada paruh kedua abad 1800-an untuk menyimpan relik Santo Paulus dari Salib (+ 1775).
Di sepanjang lorong samping terdapat berbagai monumen pemakaman.
Di lorong kiri, di belakang altar Sakramen Mahakudus, terdapat lukisan dinding yang berasal dari abad ke-12.
Akhirnya, pada awal 1950-an, berkat kemurahan hati besar dari pemegang gelar Kardinal Francis Spellman, Uskup Agung New York (+ 1967), fasad basilika dan biara kuno dipugar ke kemegahan sebelumnya.
Kompleks bawah tanah dari rumah-rumah Romawi yang dipugar dapat dikunjungi melalui pintu masuk yang berada di ketinggian oratorium lama Sang Juru Selamat Mahakudus, di sepanjang Clivo di Scauro.
