La vila de Puigcerdà té el seu origen a la darreria del segle XII. Segons un document datat el 16 de març de 1178, el rei Alfons I de Catalunya-Aragó havia fet traslladar la vila d’Ix a l’indret anomenat Montcerdà (Monte Cerdano) i concedí al bisbe d’Urgell, Arnau de Preixens, un lloc a la nova vila perquè pogués edificar una església parroquial. Cal suposar, doncs, que el temple que es fundà fou la parròquia de Santa Maria de Puigcerdà, de la qual no s’han localitzat notícies documentals fins ben entrat el segle XIII. En aquest sentit hi ha constància que els anys 1279 i 1280 el capellà de Podiocerdano contribuí a satisfer la dècima recaptada a la diòcesi d’Urgell en aquells anys. Poc després, el 2 de febrer de 1290, hi ha referència que Ramon de Santfeliu, obrer de l’església de Santa Maria de Puigcerdà, reconegué haver rebut de Guerau de Pera, fill i hereu d’Arnau de Pera, 20 sous melgoresos que el seu pare havia llegat en testament per a l’obra de l’església. El 8 de maig del mateix any, Bernat Pellicer de Puigcerdà i Ramon Morer de la Tor de Querol, mitjançant un document, es comprometeren a esculpir la porta petita de l’església de Santa Maria, que s’obria en el carrer homònim.
Al segle XIV, entre els anys 1312 i 1314, l’ecclesia Sancte Marie de Podio Ciritani consta en la relació de parròquies visitades pels delegats de l’arquebisbe de Tarragona que ha pervingut d’aquells anys. Així mateix, també figura en la relació de la dècima de la diòcesi urgellenca de l’any 1391.
Destruïda durant la guerra civil de 1936-39, la coneixem gràcies a fotografies. N’ha romàs el campanar, que fa 35 m d’alçada, amb la porta d’entrada, gòtica, composta per cinc arquivoltes en degradació i capitells ornamentats. Quan aquesta església quedà destruïda, la parroquialitat passà a la de l’antic convent de Sant Domènec.
De l’edifici destacava una porta petita, de tradició romànica, de marbre d’Isòvol. Es caracteritzava per l’absència de timpà, però era enriquit d’arquivoltes de secció cilíndrica i llises suportades per deu columnes esveltes, segons un tipus de portal molt estès a Catalunya als segles XII i XIII. Els capitells eren ornats de caps d’animals molt ben executats. Alguns elements d’aquesta portada que se salvaren de la destrucció es troben avui dia a la façana de l’església parroquial actual.
La fàbrica inicial fou molt modificada i engrandida entre els segles XIV i XVIII, època de la construcció del campanar. Les dues naus laterals, amb moltes capelles, també foren afegides en època posterior al romànic.