Sobre l’indret de la tomba s’erigí molt antigament un martyrium o santuari dedicat al sant, al qual el rei Recared (vers el 590) regalà una corona d’or votiva, que fou robada per Pau (638) i restituïda pel rei Vamba. Un conjunt de sis sarcòfags pagans i paleocristians (s. II-IV), trobats en fer la nova església i ara encastats en els seus murs interns, indiquen l’existència al lloc d’una antiga necròpoli. Després de la recuperació cristiana de Girona (795) es restaurà aquesta església i aviat s’hi establí una comunitat de preveres amb una vida canònica paral·lela i subjectada a la de la catedral. La canònica és documentada des del 882. A mitjan s. X ja consta com a comunitat amb béns propis, regida per un abat. Molts dels seus abats foren a la vegada bisbes de Vic, com Arnulf (993-1010) o Borrell (1013-17), arquebisbes de Tarragona (Berenguer de Vilademuls, 1167-94), bisbes de Girona (Guillem de Vilamarí, 1309-12) o de València (Vidal de Blanes, 1337-42). La comunitat fou reformada al s. XI, però no fou mai augustiniana i els seus membres seguiren el mateix tipus de vida que els de la catedral, fins al punt que molts dels seus membres eren a la vegada canonges d’ambdós llocs, cosa que prohibí el bisbe Arnau de Montrodon el 1337.
L’església de Sant Feliu és una barreja de planta romànica i culminació gòtica. S'inicià al s. XIII i s’acabà a la fi del XIV. Consta de planta i creuer amb dues absidioles a la part esquerra del creuer, i una de sola a la dreta. El 1313 es construí el nou absis major. Només el braç esquerre del creuer és cobert amb volta de tradició romànica, la resta ho és amb voltes de nerviacions gòtiques: el 1318 es feu la coberta del presbiteri i el 1326 la volta central. Un trifori del s. XIII entre la part romànica i les voltes gòtiques li dóna una esveltesa especial. El 1386 l’arquitecte Pere Sacoma inicià la construcció del campanar, enllestit el 1392. El seu coronament fou modificat després que un llamp hi caigué el 1561. Per la seva situació, vora la muralla de la ciutat, l’obra fou fortificada i conclosa amb caire de fortalesa per ordre del futur Pere II (1262). Tenia un claustre a la part del nord (1357-68), però fou demolit i ara ocupa el seu lloc la capella de Sant Narcís, construïda a partir del 1782. El culte a sant Narcís , pretès bisbe de Girona (307), fou sempre compartit amb el de sant Feliu. La comunitat canonical fou aviat doblada de beneficiats i porcioners i es mantingué amb força vitalitat fins al s. XVI; més endavant fou una simple col·legiata, doblada de servei parroquial. El 1806 passà a ésser simple parròquia. L’any 2008, en el curs d’uns treballs de restauració hom descobrí una sèrie de pintures murals a la volta de la nau principal, datades de finals del s. XV. L’any 2011 fou distingida pel papa Benet XVI amb el títol de basílica menor.