Il titolo dei Santi Quattro Coronati a Roma, un'istituzione simile ad una odierna parrocchia, fu fondato sulle pendici settentrionali del colle Celio forse alla fine del VI secolo. Come luogo di culto fu utilizzata un'ampia aula con abside ad ovest, che faceva parte di una ricca residenza aristocratica di età tardoantica. Il complesso ecclesiastico che si sviluppò intorno alla basilica nei secoli successivi ebbe grande importanza, dovuta principalmente al fatto di essere nelle vicinanze del Palazzo del Laterano, dove i papi ebbero per tutto il Medioevo la loro residenza ufficiale.

In età carolingia papa Leone IV (847-855) trasformò radicalmente il complesso: fece aggiungere all'aula tardoantica due navate laterali con tre oratori sporgenti e costruire una cripta semianulare. Davanti alla facciata della nuova basilica furono realizzate delle costruzioni articolate intorno ad un vasto cortile centrale, di cui sopravvivono ancora molte parti murarie, inglobate in strutture posteriori: ad est un portico ad arcate e pilastri, oggi incluso nella facciata del XVII secolo, precedeva un corpo di fabbrica costituito da una torre, poi usata come campanile, alta circa m 22, affiancata da due ampie sale rettangolari. La base della torre era traforata da arcate, mentre i lati della cella campanaria sono ancora oggi ornati da quadrifore con pilastrini di marmo. Alcune tracce di affreschi rivelano che la torre era decorata all'interno e all'esterno. Attraversando la base della torre si giungeva, come oggi, nel primo cortile, i cui lati erano probabilmente porticati. Forse sempre ad opera di Leone IV al lato destro della basilica fu addossato un edificio destinato al clero e in particolare al cardinale titolare. Il complesso ecclesiastico di Leone IV si distinse per la ricchezza dell'architettura e per le dimensioni, ben 95 m di lunghezza e 50 m di larghezza. I caratteri della basilica non si discostano dalla ripresa di forme paleocristiane tipica dell'età carolingia, mentre quelli degli edifici annessi rappresentano a Roma un unicum, che rimanda a esempi francesi e tedeschi.

A seguito dei gravi danni prodotti dall'incendio appiccato dalle truppe di Roberto il Guiscardo nel 1084, papa Pasquale II (1099-1118), abbandonato un primo tentativo di ricostruzione della basilica con le precedenti dimensioni, la fece ridurre alla sola metà ovest della ex navata centrale. Si venne così a costituire il sistema dei due cortili che precedono l'attuale basilica, il primo corrispondente in gran parte a quello del IX secolo, il secondo ricavato nella metà orientale della navata centrale carolingia (entrando sulla destra si vedono i resti delle arcate). Le ex navate laterali furono inglobate, la destra nel palazzo del cardinale titolare, la sinistra nel monastero fondato dallo stesso Pasquale II, che dal 1138 divenne un priorato dell'abbazia benedettina di S. Croce di Sassovivo presso Foligno.

La basilica pascaliana è a tre navate, divise da quattro colonne per lato con capitelli corinzi che sostengono arcate. Due grandi pilastri rettangolari raccolgono le ultime arcate e sostengono l'arco trionfale che immette nel transetto. Sopra le navatelle corrono due gallerie aperte verso la navata centrale da due trifore per lato con colonne ioniche e parapetti di marmo. L'abside è ancora quella dell'aula tardoantica, ricostruita parzialmente da Leone IV, e questo spiega le sue ampie proporzioni inadeguate al resto dell'interno. La basilica è arricchita da un pavimento precosmatesco nel quale sono state riutilizzate molte iscrizioni provenienti da un antico cimitero cristiano. Affreschi del tempo di Pasquale II ornavano l'abside e il transetto.

Nei secoli successivi la basilica fu trasformata e arricchita. La navata centrale e il transetto furono coperti da un soffitto ligneo fatto eseguire dal cardinale titolare Enrico, re di Portogallo, prima del 1580. Nelle navate laterali furono costruiti tre altari, mentre altri due sono addossati ai pilastri dell'arco trionfale; in quello di sinistra si trova un pregevole ciborio di marmo del tempo di Innocenzo VIII (1484-1492). Resti di affreschi, prevalentemente del XIII-XIV secolo, e alcune colonne della ex navata centrale sono stati messi in luce dal sovrintenedente alle Belle Arti Antonio Muñoz durante i restauri del 1913-1914.

Nel transetto si trovano gli accessi alla cripta semianulare, trasformata una prima volta da Pasquale II con la creazione di nuove scale, poi nel 1623 dal cardinale titolare Giovanni Garzia Mellini, che fece ridurre e decorare la cella delle reliquie. Il cardinale provvide anche ad una nuova decorazione dell'abside, affidata al pittore toscano Giovanni di San Giovanni: il cilindro fu ornato con paraste scanalate di ordine corinzio poggianti su di un alto stilobate, e la superfice tra le paraste, divisa in scomparti da cornici di stucchi dorati, fu affrescata con le storie dei santi Quattro. Nel catino fu rappresentata la Gloria di tutti i Santi.

Gli edifici annessi alla basilica nel '200 ebbero un notevole sviluppo. In particolare il palazzo cardinalizio fu notevolmente ampliato dal cardinale Stefano Conti, nipote di Innocenzo III. Egli fece costruire un'imponente struttura fortificata sul lato nord della basilica, che al piano terra contiene la cappella di S. Silvestro, ovvero un oratorio consacrato nel 1247 e ornato da pregevoli affreschi duecenteschi raffiguranti le storie di papa Silvestro e Costantino. Al piano superiore si trova un vastissimo salone, detto 'gotico' dalla forma delle volte a sesto acuto che lo coprono, dove è stato recentemente scoperto un ciclo di affreschi, ancora in restauro, di eccezionale interesse, databile anch'esso alla metà del XIII secolo. Dopo che la cappella di S. Silvestro nel 1570 fu acquistata dalla Confraternita dei Marmorari che aveva come patroni i santi Quattro, il presbiterio fu trasformato nella forma attuale e affrescato probabilmente da Raffaellino da Reggio; i membri della Confraternita commissionarono anche gli affreschi adiacenti all'ingresso laterale della cappella, sotto il portico ovest del primo cortile, raffiguranti la Visitazione di Maria e la Natività con la data del 1588.

Anche il monastero nel XIII secolo fu notevolmente ampliato e dotato di un chiostro cosmatesco, cui si accede oggi dalla navata sinistra della basilica. Intorno si sviluppano gli ambienti del monastero, costruiti in tempi diversi. Il chiostro è un vero gioiello in cui il linguaggio gotico si fonde con dirette citazioni dell'arte classica; è formato da quattro gallerie con archetti sostenuti da colonnine binate con capitelli a foglie piatte. Dalla galleria est si accede alla cappella di S. Barbara, in origine uno degli oratori della basilica carolingia, ornato da mensoloni marmorei del IX secolo e da affreschi dell'IX e XIII secolo.

Nel XIV secolo il palazzo cardinalizio fu in parte abbandonato a causa dell'allontanamento della Curia ad Avignone. Al ritorno a Roma di Martino V il cardinale Alfonso Carillo (1423-1434) fece importanti lavori di restauro, ma il trasferimento della sede pontificia dal Laterano al Vaticano influí negativamente sull'importanza del complesso. Così nel 1564 Pio IV affidó la chiesa e tutti gli edifici annessi all'Arciconfraternita di S. Maria della Visitazione degli orfani perché li trasformasse in un monastero destinato ad accogliere le fanciulle romane orfane, vigilate da Monache agostiniane. L'Arciconfraternita tra il XVI e il XVII secolo provvide ad adattare le strutture alla nuova funzione. Le modifiche furono però più esteriori che sostanziali e i muri medievali costituiscono ancor oggi gran parte dell'ossatura muraria. Tra gli interventi va ricordato l'ammodernamento dei due cortili. Nel primo nel 1632 sui lati nord e ovest furono realizzati due porticati a volte su pilastri cruciformi sormontati da un altro piano. Tutti gli ambienti che affacciano sul cortile furono trasformati in dormitori per le orfane. Nel secondo cortile davanti all'ingresso della basilica fu costruito un profondo porticato, che probabilmente riutilizza strutture del tempo di Pasquale II, al di sopra del quale fu realizzato il coro per la monache.

Nei secoli XVIII e XIX continuò la funzione di assistenza alle orfane, mentre gli interventi edilizi furono estremamente ridotti. L'orfanotrofio fu soppresso alla fine dell'800 e il complesso fu diviso in due parti, assegnate a diversi ordini religiosi femminili. La zona ovest rimase sempre affidata alle Monache agostiniane, mentre quella est dopo vari passaggi è attualmente occupata dalle Piccole Sorelle dell'Agnello.

A partire dal 1913, grazie al Sovrintendente Antonio Muñoz, cominciò la rivalutazione del monumento, con lo studio e il restauro delle fasi medievali, che continua tutt'oggi.

.