La première église est établie sur un terrain acquis par la commune et à cette occasion, une nouvelle rue est tracée dans son axe, l'actuelle rue de Mora. Le principal donataire pour sa construction est la veuve de Joseph Moreno de Mora qui habite la commune voisine de Montmorency. Elle offre 50 000 francs pour ce projet et demande que le vocable Saint-Joseph soit choisi en hommage à son époux défunt. L'église fut construite entre 1858 et 1860 sur les plans de l'architecte Auguste Delaporte qui, partant à l'étranger, laisse le chantier à Antoine-Gaëtan Guérinot (1830-1891), élève de Viollet-le-Duc. Si l'on ne construit, dans un premier temps, qu'une nef à quatre travées, l'agrandissement de l'édifice par des bas-côtés et prévu dès la conception. En 1866, le projet d'un premier agrandissement est engagé par Guérinot. Plusieurs solutions sont proposées, dont la construction d'un transept de deux travées orientales avec un nouveau chœur. Finalement, c'est l'orientation initiale qui est retenue avec la réalisation de bas-côtés et la modification de la base du clocher pour lui assurer à la fois une plus grande solidité et offrir une façade plus harmonieuse. L'entreprise de travaux publics Pascal Franco (localisée à Nurcourt en Seine-et-Oise) commence à construire un premier bas-côté, ouvrant les murs gouttereaux entre les piles jusqu'aux arcs de décharge pour élever les chapelles, éclairées par des baies jumelles surmontées d'un arc formeret. Les sculptures sont alors exécutées par le sculpteur parisien Bernard. Les travaux, faute de financement, s'achèvent difficilement en 1868. L'inventaire des biens de la paroisse de 1906 (AD Val d'Oise 1V 616) signale la présence d'une pierre à l'intérieur au dessus du portail d'entrée portant l'inscription : cette église a été dressée à la mémoire de M. Joseph de Moreno de Mora par Marie de Mora et ses enfants M. Pascal M. de Mora, Mme Gil de Mora et M. Jean M. de Mora, 22 avril 1857. L'église devenant trop exiguë pour le nombre de paroissiens, l'abbé Simonin demande dès 1926 un second agrandissement. Plusieurs projets sont présentés, dont celui de l'architecte Albert Guilbert. Finalement, ce sont les architectes associés Albert Morize, Jean Lacour et René Boutin qui sont choisis. Ils travaillent en collaboration avec l'architecte municipal Henri Moreels. Parmi les différents projets proposés par les architectes (extension sur la place sans modification de l'ancien clocher, construction d'un triforium sur les côtés), celui adopté propose la mise en place d'un nouveau clocher, l'ajout de deux travées et l'ouverture de quatre portes supplémentaires. Les premières élévations, dans un style moderne proche d'Auguste Perret, ne plaisent pas à l'abbé Simonin, qui demande que l'édifice s'inspire de l'église Notre-Dame de Poitiers dans un style romano-byzantin. De la façade poitevine, les architectes ne reprendront que quelques éléments (façade pignon couronnée par deux frontons triangulaires imbriqués et surtout présence de deux clochetons latéraux, bien que très réinterprétés à Enghien). Les travaux sont confiés aux entreprises de maçonnerie Robert Feiss (8, rue Brune à Paris) et J. Peignin (Saint-Denis).