La basilica, con orientamento est-ovest, è costituita da strutture di epoche differenti: campanile, atrio d’ingresso, due absidi contrapposte, edicola mosaicata, cappella Sancta Sanctorum, navate. La complessa stratificazione ha avuto origine alla fine del III secolo, quando S. Felice fu sepolto in una tomba in laterizi dotata di cuscino funebre e incavo per l’appoggio della testa. Agli inizi del IV secolo, il venerato sepolcro, insieme a due adiacenti tombe (appartenute forse ai vescovi Massimo e Quinto), venne racchiuso in un piccolo mausoleo quadrato e protetto da una lastra di marmo decorata dall’immagine del Buon Pastore. Il mausoleo, insieme ad altri due adiacenti ambienti funerari, fu demolito dopo l’anno 313 per costruire il primitivo edificio di culto (aula ad corpus) che aveva l’abside a nord e l’ingresso a sud, in direzione della città di Nola. Intorno alla metà del IV secolo, ad est dell’aula fu realizzata una basilica a tre navate con abside ad est (basilica orientale). Tra il 401 e il 403, Paolino di Nola, demolita l’abside dell’aula ad corpus, costruì una triplice apertura (triforium) che consentiva l’accesso all’atrio di un nuovo e più grande edificio di culto che egli chiamò basilica nova. Il presule provvide, altresì, a decorare adeguatamente l’aula ad corpus, dove la tomba di S. Felice venne delimitata da transenne marmoree con massime bibliche. Dopo la morte di Paolino, avvenuta il 22 giugno 431, il recinto di transenne fu prima ampliato verso sud per includere il suo sepolcro e quindi trasformato in un grande altare. Tra il 484 e il 523, intorno alle tombe di Felice e Paolino, venne costruita l’edicola mosaicata: si tratta di una struttura costituita da quattro pareti in laterizi, ciascuna delle quali presenta tre archi sostenuti da colonne e capitelli di reimpiego. Forse nello stesso periodo, ma comunque successivamente all’alluvione degli inizi del VI secolo, ad ovest dell’aula ad corpus sui resti di tre mausolei funerari fu eretta la grande abside occidentale. Tra VIII e IX secolo, a seguito del crollo della basilica nova, il triforium paoliniano venne murato e nell’arco centrale fu edificata la cappella Sancta Sanctorum. Pressappoco nello stesso periodo l’altare sulle tombe di Felice e Paolino venne violato dai Longobardi. Mentre il corpo di S. Paolino fu traslato a Benevento, le ossa di S. Felice vennero in parte trasferite all’interno del ricostruito altare e in parte in un reliquario creato alle spalle dell’altare. Tra la fine del IX secolo e gli inizi del successivo, sul lato meridionale della basilica di S. Felice il vescovo Leone III costruì un protiro che nel Trecento venne inglobato nel nuovo atrio di ingresso. Nel medioevo la basilica venne interessata da interventi strutturali e decorativi commissionati dal clero e dalla nobiltà locale. Oltre a numerosi affreschi, vennero realizzati nuovi altari e il pulpito.
Nel 1631 l’eruzione del Vesuvio danneggiò il presbiterio orientale e la navata destra della basilica, mentre la sinistra crollò alla fine del Seicento, ma venne ricostruita entro gli inizi del secolo successivo. In quell’occasione il principe Girolamo II Albertini ampliò l’edificio verso est e lo arricchì di stucchi e dipinti. Alla fine del Settecento le navate e il presbiterio orientale della basilica furono in massima parte abbattuti per costruire la nuova chiesa parrocchiale. Ulteriori pesanti demolizioni hanno interessato, negli anni Trenta e Cinquanta del XX secolo, l’edicola mosaicata e l’abside occidentale. In occasione del Giubileo del 2000 la Soprintendenza Archeologica di Napoli e la Soprintendenza per i Beni Architettonici e Ambientali hanno realizzato all’interno della basilica un antiquarium nel quale sono custoditi reperti di età romana, paleocristiana, medievale e postmedievale provenienti dal complesso.