L'attuale basilica è frutto di fondazioni sovrapposte. La prima, sorta sui resti di un cimitero romano, risale al IV secolo e fu dedicata ai santi martiti Felice e Fortunato; la seconda a tre navate è del V secolo e la terza, che di fatto occupa l'area della chiesa precedente, fatta eccezione per l'abside, è romanica (X-XII secolo).
Qualche successivo intervento risale alla prima metà del Quattrocento, al Seicento, fino agli scavi e ai restauri novecenteschi.
Nella chiesa vi passò Carlo Magno nell'802. Nel 899 fu distrutta dagli Ungari, motivo per cui nel 975 il vescovo Rodolfo ne promosse la ricostruzione, affidandola ai monaci benedettini.
La facciata, con resti di affreschi di XI secolo, è in cotto e su di essa spicca il portale che l'iscrizione precisa essere del 1154 e opera di Pietro Veneto.
Il campanile, che alla base presenta conci d'epoca romana, venne costruito nel X secolo ma in gran parte rifatto dopo il terremoto del 1117.
All'interno, nel Martyrion si conservano le reliquie di san Felice da Aquileia, mentre tra le decorazioni si segnalano opere di Antonino da Venezia e di Giulio Carpioni.
Dal 2005 è stato aperto un museo che conserva i reperti romani e paleocristiani rinvenuti sul sito.