D’abord simple chapelle castrale attribuée à Mathieu I de Montmorency (v. 1100 – 1160), sa première construction se situerait entre 1124 et 1160. La date de 1137 est souvent retenue. On pense que le souci de donner à sa famille une sépulture digne de son rang et la proximité de la nécropole royale de Saint-Denis le décidèrent à cette édification. Il devait tenir à en faire un édifice cultuel important puisqu’il décida d’y attacher un chapitre de neuf chanoines, d’où son appellation de collégiale.
Bien qu’on ignorât l’aspect de ce premier édifice, sa configuration devait être très proche de la collégiale actuelle puisque celle-ci a été édifiée sur ses fondations. On peut aussi raisonnablement penser que son architecture subit l’influence du gothique primitif. De cette première construction, il ne reste que quelques éléments lapidaires retrouvés lors les travaux au 19ème siècle, et qui sont conservés au Louvre.
Outre être dédiée à Saint-Martin, dédicace qui reste un mystère, Saint-Félix était son second patron. Objet d’une vénération toute particulière à Montmorency, des reliques de ce saint étaient conservées dans une châsse derrière le grand autel.
De multiples aménagements furent ensuite apportés, mais il semble que seul Mathieu IV (1252 – 1304) ait réellement porté un intérêt à l’édifice en ordonnant des réparations urgentes. Après le siècle d’or que fut le 13ème siècle, la France s’enfonça dans l’une des plus sombres périodes de son histoire, notamment avec la Guerre de Cent ans, la peste noire, les famines, etc. Comme tous les environs de Paris, Montmorency fut le théâtre de pillages et de nombreuses jacqueries dont la collégiale fut victime.
Durant cette période, l’intérêt des Montmorency pour leur baronnie semble avoir été assez faible, l’action essentielle étant la reconstruction, par Jacques II en 1411, des remparts de la ville détruits par les Anglais.
Quand le calme revint, la collégiale, qui avait servi de cantonnement à la soldatesque et n’était plus entretenue depuis longtemps, menaçait ruine. En outre, les Montmorenciens s’en étaient d’autant plus désintéressés qu’ils disposaient de deux autres édifices cultuels à usage local: l’église Notre-Dame et l’église Saint-Jacques.
Aux alentours de 1515, Guillaume de Montmorency, peut-être en mémoire de son père, Jean II, restaura la collégiale pour qu’elle devienne une nécropole de famille.Suivant un parti ambitieux, dans un style gothique flamboyant, en tenant compte de divers documents, notamment des contrats et des mémoires des marchés de travaux, la date de 1525, souvent donnée comme le début de la reconstruction, serait plus probablement celle de sa fin pour au moins une bonne partie. Par ailleurs, il conclut le marché de son tombeau février 1524. Il incomba ensuite au connétable Anne de Montmorency le soin de faire construire la nef , à partir de 1557, dont il confia le chantier à Jean Bullant. Celui-ci, dans un souci d’harmonisation, tout en le simplifiant, respecta le style du premier architecte. La date de 1563 est inscrite sur la voûte, mais les travaux ont dû se poursuivre jusqu’à la mort du connétable en 1567.