La VMI réunit deux lignes à l'histoire spécifique : la ligne d'Auteuil, devenue partie intégrante de la ligne de Petite Ceinture dans Paris intra-muros, et la ligne Ermont - Eaubonne - Plaine - Gare du Nord via Gennevilliers au nord, dite ligne La Plaine - Ermont-Eaubonne ou ligne des Grésillons.
La ligne d'Auteuil a été construite à l'initiative des frères Pereire, qui avaient déjà réalisé la ligne de Saint-Germain-en-Laye ; elle est mise en service par la compagnie des chemins de fer de l'Ouest le 2 mai 1854. En 1867, elle est incorporée dans la ligne de Petite Ceinture, construite en différentes étapes autour de la capitale.
La ligne Ermont-Eaubonne - Plaine - Gare du Nord via Gennevilliers est mise en chantier en 1905 et inaugurée avec ses deux raccordements le 1er juillet 1908. Un grand soin est apporté à l'édification des bâtiments voyageurs, largement dimensionnés et à l'architecture élégante.
À partir du 25 septembre 1977, les trains restent limités au parcours Saint-Ouen-Garibaldi - Ermont-Eaubonne, en raison du démarrage des grands travaux en avant-gare du Nord, en vue de la création de la gare souterraine du futur RER et de l'interconnexion Nord-Sud.
La transversale Nord-Sud Saint-Lazare - Montparnasse du RER prévue au SDAU de 1965 est abandonnée au vu de son coût, et la desserte de Cergy est finalement assurée par un débranchement de la banlieue Saint-Lazare. La vallée de Montmorency, zone urbanisée de 250 000 habitants au nord de Paris, reste par conséquent sans desserte performante de type RER. Trois dessertes sont ainsi étudiées au milieu des années 1970 :
Les difficultés d'insertion d'une nouvelle desserte dans la trame saturée de la banlieue Saint-Lazare font privilégier la troisième solution.
Le projet VMI est mis au point par la SNCF au début de 1977. Opération majeure relevant du programme spécial, elle a été présentée et prise en considération par le syndicat des transports parisiens (STP) le 28 septembre 1977. La nouvelle liaison projetée intègre l'essentiel de la ligne Ermont - Saint-Ouen-les-Docks au nord et de la ligne d'Auteuil au sud. Elle utilise essentiellement des lignes existantes à moderniser, avec réactivation du raccordement neutralisé de Boulainvilliers au sud et la construction d'un nouveau raccordement aux Épinettes, seule section nouvelle, qui permet de relier la Petite Ceinture à la ligne des Docks. Selon les premières études, la ligne serait employée par quarante-cinq millions de voyageurs annuels, avec un gain de temps moyen de huit minutes par trajet. On estime, par ailleurs, que 3700 usagers abandonneraient leur voiture au profit du train.
Avec l'aval du STP, la SNCF aurait pu directement proposer le projet à l'enquête d'utilité publique. Toutefois, au vu de la levée de boucliers provoquée contre le tracé aérien dans le quartier des Épinettes, la SNCF revoit d'elle-même le projet avant de le soumettre à l'enquête préalable à la déclaration d'utilité publique, début 1980. La ligne est enfermée dans un tunnel de verre, selon un tracé bien moins favorable, mais annihilant toute nuisance acoustique pour les riverains. Mais la Ville de Paris critique à son tour le projet, en particulier le tunnel de verre censé provoquer une coupure dans la trame urbaine et réclame en outre la couverture de la tranchée Pereire.
La commission d'enquête tient compte des demandes des riverains et de la mairie de Paris : au printemps 1980, elle réclame une couverture légère de la tranchée Pereire et refuse le tunnel de verre aérien, ce qui impose à la SNCF de revoir une nouvelle fois très rapidement sa copie.
L'important surcoût de 110 millions de francs engendré par un tracé souterrain au Épinettes provoque les plus vives inquiétudes qui vont jusqu'à envisager l'annulation du projet. Finalement, plusieurs mesures sont prises afin de limiter la dérive des coûts :
Le produit de la vente à la Ville de Paris du raccordement des Batignolles est reversé au budget VMI, afin de financer une couverture lourde de la ligne d'Auteuil. La déclaration d'utilité publique est enfin prononcée de justesse après ces aménagements, avant le délai de péremption légal de l'enquête, le 25 septembre 1981.
Mais c'est alors au tour de la ville de Saint-Ouen d'émettre des exigences ; elle souhaite voir la ligne traverser la commune en souterrain. Soutenue par le ministre des Transports de l'époque, le communiste Charles Fiterman, elle contraint la SNCF à réexaminer une nouvelle fois son projet. La ville est alors traversée en tranchée couverte, avec la construction d'une nouvelle gare entièrement souterraine. Le projet est enfin adopté en septembre 1984.
Les exigences des riverains ont fait tripler la facture en francs constants, retarder les travaux de six ans et rendu le tracé en plan ainsi que le profil particulièrement médiocres, très loin de la norme appliquée aux nouvelles infrastructures des lignes A et B du RER et prévues à l'origine. Ainsi, la vitesse dans les inter-stations dans Paris est limitée à 60 voire 40 km/h au lieu des 90 km/h prévus. Les gares de Porte-de-Clichy et Saint-Ouen, initialement prévues au sommet d'une rampe, se retrouvent en cuvette encadrées de fortes rampes, dont certaines atteignent les 40‰.
Le chantier de la VMI démarre enfin en 1985. Sa grande complexité conduit au partage de la maîtrise d'œuvre. La région de Paris-Nord assure la mise à niveau des lignes Ermont - Argenteuil (4 km), et de la ligne des Docks (10 km). Le tronçon de Saint-Ouen au Champ-de-Mars (9 200 m) est confié à un « groupe d'études travaux » (GET) relevant de la région de Paris-Saint-Lazare.
La modernisation du court tronçon Ermont - Argenteuil avec électrification en 25 kV ne pose pas de difficultés et est réalisée de manière anticipée dès mai 1983. En revanche, la modernisation de la ligne La Plaine - Ermont-Eaubonne est bien plus longue, car l'infrastructure est loin du niveau exigé pour une desserte cadencée moderne. En 1983, les ponts-rails sont restaurés et le raccordement des Épinettes est supprimé. La voie est entièrement renouvelée d'Ermont à Saint-Gratien en 1984 avec modification du plan des voies de la gare d'Ermont - Eaubonne. En 1985, c'est au tour du tronçon Saint-Gratien - Saint-Ouen.
Le block Lartigue Nord uniformisé encore en place de Gennevilliers à Ermont laisse la place au block automatique lumineux (BAL), déjà installé sur le tronçon Gennevilliers - La Chapelle pour les besoins du trafic fret. L'itinéraire est doté de deux pas d'installations permanentes de contre-sens (IPCS), accompagnés d'un poste d'aiguillage type PRCI, établi à Gennevilliers durant l'été 1987. Parallèlement, tous les bâtiments voyageurs sont profondément modernisés ou reconstruits, avec rénovation complète des quais, de l'éclairage, des abris et de la signalétique. La gare de Gennevilliers est reconstruite cinq cents mètres plus au sud en 1986, afin d'être mieux située sur les itinéraires de transports, en particulier le futur prolongement du tramway T1 de Saint-Denis à Asnières - Gennevilliers, l'ancien bâtiment voyageurs est revendu puis converti plus tard en restaurant McDonald's. Un bâtiment voyageurs est édifié aux Grésillons et un saut-de-mouton est construit à Saint-Ouen.
Les travaux dans Paris sont quant à eux particulièrement délicats. Le sous-sol est traversé d'une multitude de canalisations et conduites diverses, ce qui complique les travaux. La section réutilisée de la ligne d'Auteuil est totalement rénovée : les voies sont déposées et renouvelées, les quais reconstruits et les sections en tranchée encore à l'air libre sont recouvertes d'une dalle de béton afin d'éviter toute « pollution sonore » pour les riverains. Pourtant, comme le souligne A. Jacquot, les dalles déjà en place autour de la gare de l'avenue Henri Martin sont utilisées comme parcs de stationnement, la pollution auditive de la circulation n'est donc pas prise en compte. Les bâtiments voyageurs ainsi que les couloirs souterrains sont entièrement restaurés.
Entre la ligne des Docks et la ligne d'Auteuil, un tunnel à double voie, avec un emplacement réservé pour la gare de la Porte de Clichy, est mis en chantier. Entre Pereire et le pont Berthier, il ne subsistait plus de la gare de Courcelles-Ceinture qu'une voie unique, dite « voie des Souverains ». Suite à une opération immobilière le long de la plate-forme durant les années 1950, il ne restait même plus la place pour une double voie au gabarit UIC, il manquait cinquante centimètres. Ce manque de prévoyance impose de lourds travaux entrepris d'octobre 1984 à mai 1985. Il est nécessaire d'abaisser le radier pour dégager le gabarit électrification, et d'élargir la tranchée par la reprise de l'ancienne paroi inclinée. En 1987, la section à l'air libre située à l'ouest du pont Berthier est recouverte d'une dalle de protection phonique, immédiatement utilisée comme parc de stationnement automobile, dont le bruit et la pollution ne semblent là encore pas pris en considération.
Au sud, le viaduc sur la Seine, dit pont Rouelle, est entièrement reconstruit en 1982 en respectant le style d'origine mais avec un tirant d'air plus important pour la navigation fluviale ; les poteaux caténaires font l'objet d'une recherche esthétique pour une meilleure intégration paysagère. Un saut-de-mouton est édifié sur la rive gauche à la bifurcation du Champ-de-Mars afin d'éviter les cisaillements de voies. Pour limiter le bruit pour les riverains, pourtant inférieur à celui permanent provoqué par l'importante circulation routière sur les quais, ce saut-de-mouton est recouvert d'un coffrage en béton. Enfin, la ligne est dotée du BAL avec IPCS.
Les travaux avancent conformément au planning sur le tronçon Nord de Saint-Ouen à Ermont ; en revanche, la complication des travaux dans Paris retarde ceux du tronçon Saint-Ouen - Champ-de-Mars, de plus liés à l'arrêt du service sur la ligne d'Auteuil, effective le 7 janvier 1985 avec remplacement par une navette routière.
Le 1er août 1987, le BAL et les IPCS sont mis en service sur la ligne des Docks, avec le nouveau PRCI de Gennevilliers puis du poste PRCI de Saint-Ouen-les-Docks le 27 août 1987, normalement télécommandé depuis Gennevilliers. Toutes les autres mises en service s'étalent durant l'année 1988.
L'électrification en 25 kV-50 Hz monophasé de La Chapelle à Ermont est mise sous tension le 21 juin 1988 ; trois jours après, le tronçon Saint-Ouen - Champ-de-Mars voit la mise en service du BAL et des IPCS, le nouveau poste d'aiguillage type PRS de Pereire étant télécommandé par le poste d'aiguillage et de régulation (PAR) des Invalides.
Le 18 août 1988, le même tronçon sud est mis sous tension, en 1500 V continu, ainsi que l'antenne Pereire - Pont-Cardinet. La liaison Vallée de Montmorency - Invalides, nouvelle branche nord-ouest du RER C, est enfin mise en service pour le service d'hiver le 25 septembre 1988. Elle dessert la banlieue nord-ouest, en direction de Montigny - Beauchamp et Argenteuil.
Le nouvel itinéraire est géré par la région de Paris-Sud-Ouest jusqu'à la section de séparation des deux tensions d'alimentation, à Saint-Ouen, et par la région de Paris-Nord, au-delà. Le kilométrage de la ligne est harmonisé, avec un PK 0 à la gare des Invalides, jusqu'à Argenteuil au PK 25,428 km, via Ermont. En septembre 1991, la gare de Porte de Clichy dont les travaux avaient été retardés pour cause d'absence de financement, est à son tour mise en service.
Le 28 août 2000, le service est prolongé de Montigny - Beauchamp à Pontoise, chef-lieu du Val-d'Oise en empruntant la ligne Ermont - Pontoise. Le 27 août 2006, dans le cadre de la liaison directe Paris-Saint-Lazare - Ermont-Eaubonne, la ligne C perd sa courte branche Argenteuil (C3), avec réorientation de la totalité des trains vers la ligne de Pontoise.