Il Coelius Maior (Celio Maggiore) per lunghi secoli rimase un colle quasi del tutto disabitato. Vi pascolavano le greggi, tra gli orti e le vigne. Posta su questo colle antico, a sinistra dell’antico clivo di Scauro, la basilica sorse negli ambienti abitativi dei fratelli ufficiali Giovanni e Paolo, molto influenti a corte, trucidati per la fede cristiana il 26 giugno 362, al tempo dell’imperatore Giuliano l’Apostata (+ 363). Questi ambienti rappresentano un unicum nella storia dell’archeologia romana. Essi conservano tracce del primitivo culto cristiano insieme ad altre più vistose vestigia dell’arte precedente.
     Dopo l’uccisione dei fratelli, altri cristiani martiri vi vennero deposti: Crispo, Crispiniano e Benedetta. La venerazione dei santi martiri celimontani si concretizzò alla fine del IV secolo in un edificio cultuale ad corpora per opera del senatore Bizanzio. Successivamente il figlio del senatore, Pammachio (+ 410c.), amico di san Girolamo, sviluppò l’edificio in forma basilicale magna et valde formosa (grande e molto bella) come recita l’Itinerario di Salisburgo. Saccheggiata e rovinata al tempo dei Visigoti nel 410, nei secoli VI e VII era sempre frequentata dai pii pellegrini. Venne anche dotata di numerosi benefici. I nomi degli ufficiali martiri vennero inseriti nel Canone Romano. In Roma si trovavano altre due chiese intitolate ai martiri celimontani. Una di queste si trovava sul colle Gianicolo. L’altra, con annesso monastero, venne edificata da san Leone Magno verso il 440, nella zona attualmente occupata dalla crociera dei ss. Processo e Martiniano della basilica di san Pietro.
     Due sacerdoti, Proclinus e Ursus, ne ebbero il titolo durante il pontificato di papa Innocenzo I (+ 417). Quattro presbiteri, due del titolo di Bizanzio e due del titolo di Pammachio, parteciparono al sinodo romano del 499. Secondo il catalogo di Pietro Mallio, stilato sotto il pontificato di papa Alessandro III (+ 1181), il titolo, in quel periodo, era collegato alla basilica di San Lorenzo fuori le mura ed i suoi sacerdoti vi celebravano messa a turno. La basilica venne restaurata più volte. Già papa Simmaco nel V secolo e poi Leone III se ne occuparono. Il culto dei martiri celimontani era diffuso ormai in tutta la Chiesa. Un lettore, tale Massimino, morto nel 567 a 20 anni, esercitava il suo ministero in questa basilica. Il servizio liturgico era assicurato da una piccola comunità canonicale (o monastica) nei secoli a cavallo dell’anno Mille.

     Dopo il 1118 terminarono i lavori di restauro della basilica e di ampliamento della monastero ordinati dal titolare, il cardinale Teobaldo, al tempo di papa Pasquale II (+ 1118), dopo i danni causati dai Normanni di Roberto il Guiscardo. Oltre l’usura del tempo, vari terremoti fecero dei danni rilevanti. Anche il portico ionico, sorretto da otto colonne con capitelli ionici, risale al XII secolo (costruito in sostituzione dell’antico nartece), così come l’abside furono completati dal cardinale Giovanni dei Conti di Sutri (1216) e da Adriano IV. Il campanile venne edificato nel 1115.
     Altro importante e profondo restauro nel 1718 (architetti Antonio Canevari e Giovanni Andrea Garagni, piemontese), conferì all’interno della basilica la forma attuale, fu voluto dal cardinale Fabrizio Paolucci (+ 1719) e stravolse completamente la forma “aperta”, molto luminosa, della basilica paleocristiana. Trasformazione già iniziata con il cardinal Philip Howard nel secolo precedente.
     L’interno della basilica è ampio e maestoso, ripartito in tre navate da colonne a vista e da pilastri. Il pavimento è cosmatesco. A pochi metri dell’entrata, nella navata centrale, una lastra marmorea ricorda il luogo sotterraneo del martirio. Le reliquie dei ss. martiri riposano sotto l’altare maggiore in un’urna preziosa di porfido. Sulla navata di destra è stata costruita nella seconda metà del 1800 una fastosa cappella dove sono custodite le venerate reliquie di san Paolo della Croce (+ 1775). Lungo le navate si possono osservare vari monumenti funebri. Nella navata di sinistra, dietro l’altare del SS. Sacramento, si conservano affreschi del secolo XII.
     Finalmente nei primi anni ’50 del secolo scorso, per la munificenza del cardinale titolare Francis Spellman, arcivescovo di New York (+ 1967), le facciate della basilica e dell’antico monastero vennero riportate al loro antico splendore. Gli ambienti sotterranei, restaurati, sono visitabili attraverso l’ingresso posto all’altezza dell’antico oratorio del Crocifisso, lungo il clivo di Scauro.