Les primeres notícies fidedignes que trobem sobre el temple de Santa Maria de Vilafranca daten de l'any 1187, quan apareix citada en el testament de Pere de Vilafranca. Alguns estudiosos creuen que l'església de Santa Maria fora de Muralla, que s'esmenta en l'acta de consagració de Sant Miquel d'Olèrdola de l'any 992, podria ser aquest temple.

En 1188 el rei Alfons I va donar a l'església de Vilafranca el dret de les notaries i de la vila i de tot el seu terme. Això i el fet que Vilafranca es convertí en allotjament reial, quan els monarques estaven de pas pel Penedès, va fer que el poder de la vila i de la seva església augmentessin considerablement. Això desencadenà en la construcció d'un nou temple, més adient al nou estatus de Vilafranca. La primera pedra es va col·locar en el mes de maig de 1285. Les obres de construcció es van perllongar fins l'any 1484, moment en que fou consagrada.

Es tracta del primer edifici parroquial construït integrament en estil gòtic de Catalunya. Està formada per una amplia nau, dividida en cinc trams i acabada en un absis poligonal, seguint l'esquema habitual del gòtic català.

Els nervis de les voltes de creueria descansen en columnes adossades als grans contraforts dels murs laterals. L'espai existent entre els contraforts es va aprofitar per construir-hi capelles laterals, cobertes amb voltes de canó apuntades i il·luminades per grans finestrals. Els seus vitralls són de mitjans segle XX, doncs els originals es van perdre l'any 1934 en un incendi.

La seva façana actual és d'estil neogòtic i va ser construïda l'any 1905, substituint a una galeria porticada renaixentista. També es van construir les dues torres que la flanquegen i es va engrandir la rosassa que la presideix.

Fins aquell moment l'entrada principal era la que està situada davant l'actual carrer de Santa Maria. Antigament era coneguda com a porta dels capellans.

És del segle XIII i mostra la transició entre el romànic i el gòtic. Les seves formes, amb arquivoltes de mig punt, encara ens recorden la construcció romànica, però la finesa de les seves traces i la seva decoració són clarament gòtiques. En alguns punts, tot i que molt malmesa, encara es conserva la policromia original.

Sota el presbiteri es va construir l'any 1561 una cripta per tal d'acollir el Santíssim Sagrament, però des de l'any 1700 acull les relíquies de Sant Fèlix, patró de la ciutat. L'actual altar de Sant Fèlix i el grup escultòric de l'Enterrament de Crist són obra de l'escultor Josep Llimona i foren donats pel bisbe Torras i Bages.

També es va afegir a l'obra original la torre campanar, situada junt a la capçalera i que és una obra del segle XIX.

En 1920, el papa Benet XV li va atorgar la categoria de Basílica Menor.