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.
