Le cimetière tire son nom de l'église de la paroisse (et du quartier) Notre-Dame. Cette dernière, débutée en 1684 et achevée en 1686, remplace l'église Saint-Julien de Brioude, détruite en 1679[1], lieu de culte initial du hameau de Versailles.
Créé en 1679 rue de la Paroisse, et originellement dénommé « cimetière Saint-Louis », il fut transféré en 1777 à son actuel emplacement, à l'occasion du comblement de l'étang de Clagny[2], dont le château est détruit en 1736.
La « Déclaration du roi concernant les inhumations », du 10 mars 1776[3] marque l'interdiction de principe, en France, des sépultures près des lieux de culte et des habitations.
Par un arrêt du Conseil du roi du 2 mars 1777[2], Louis XVI accorde un terrain récemment asséché, prélevé sur la plaine de Glatigny. Il décide également de la création d'une nouvelle rue, alors dénommée rue Saint-Lazare (initialement rue La Bruyère[4]) reliant la rue de la Paroisse et le boulevard de la Reine, entre le boulevard du Roi et la rue Neuve Notre-Dame.
Versailles est alors l'une des premières villes à écarter les cimetières de son espace urbain[5].
Le cimetière est étendu à deux reprises, en 1845 puis en 1854. Il fait l'objet d'un arrêt du Conseil d'État, en 1880. Le principe des concessions est posé en 1897 et confirmé par un arrêté municipal du .
L'ossuaire est créé en 1986.
Le cimetière comprend des sépultures aristocratiques, d'anciennes familles de Versailles ou encore, de membres de congrégations religieuses, ainsi que des tombeaux de personnalités dont beaucoup sont dignes d'intérêt artistique ou historique. S'y trouve également un enclos militaire de soldats de l'armée prussienne tombés pendant la guerre de 1870.
C'est ainsi le plus ancien des quatre cimetières de la ville[5].
L'emprise se trouve au nord de la ville à la limite de la commune limitrophe du Chesnay. Le seul accès au cimetière se fait par le 15 de la rue des Missionnaires, sur le territoire de la commune de Versailles. Le cimetière est bordé au nord par la rue du Colonelde Bange, laquelle ne permet donc pas d'y accéder.
Jean-François Lambinet (1783-1864), marchand de drap et maire de Versailles. Sur sa tombe est inscrit : Il eut le courage d'être Maire de Versailles en 1848 ; son fils, Victor Lambinet (1813-1894) avocat dont l'hôtel particulier est l'un des musées de Versailles, repose également au cimetière Notre-Dame,
Ovide Rémilly[12], (1800-1875), avocat, longtemps maire de Versailles, a fait élever la statue du général Hoche sur la place versaillaise du même nom, en souvenir de l'amitié de celui-ci pour son père[13],
Édouard Bertrand (1836-1885), fondateur de l'école industrielle de Versailles[réf. nécessaire],
Alexandrine-Nathalie de Woyda, "générale de Pankratieff" (1819-1886), veuve du général russe Nicias de Pankratieff,
Lucien Richard de Jouvance (1851-1886), architecte[réf. nécessaire].
Edmé Pierre Cougny (1818-1889), professeur de rhétorique et de philosophie au lycée de Versailles, au lycée Henri IV puis au lycée Saint-Louis, helléniste et inspecteur d'académie[18],
écrivaine et éditrice, dont la tombe porte simplement son prénom, aux côtés de ses parents, Ferdinand Loviton (1876-1942) et Denyse Pouchard (1876-1935), et de sa fille adoptive Mireille Fellous Loviton (1923-2020)
↑Jean Eckard, Recherches historiques et biographiques sur Versailles ; biographie sommaire des personnes illustres, célèbres, remarquables, etc., nées dans cette ville, (lire en ligne).
↑Laurent Mauron, « Versailles : un hommage à Albert Joly, défenseur de la laïcité : Le Cercle Albert Joly évoquera aussi Samuel Paty en déposant une gerbe sur la tombe de ce parlementaire versaillais du XIXe siècle », Le Parisien, édition des Yvelines, (lire en ligne, consulté le ).