Der erste bekannte Vorschlag für eine Verbindung von Koblenz über Mayen und weiter durch die Eifel bis nach Wittlich stammt bereits aus dem Jahr 1856. Nach Ausarbeitung der Planungen und umfangreichen Bauarbeiten konnte gut 22 Jahre später am 1. April 1878 die Strecke von Andernach nach Niedermendig eröffnet werden, der folgende Abschnitt bis Mayen folgte kurz darauf am 29. Mai 1880.

Bereits während der Bauarbeiten des zweiten Abschnittes wurde über eine Verlängerung der bestehenden Strecke nachgedacht. Dabei stand v.a. die Erschliessung der Eifel von Rhein oder Mosel aus mit Anbindung an die Eifelstrecke Köln - Trier im Vordergrund. Die damalige Eisenbahndirektion Köln erhielt am 6. Mai 1881 den Auftrag zu Vorerhebungen für eine Strecke von Gerolstein nach Mayen oder alternativ Remagen. Bevorzugt wurde jedoch zur Anbindung von vorhandenen Gesteinslagerstätten die Mayener Variante, die nach ersten Berechnungen 8,5 Millionen Mark kosten sollte.

Zunächst drohte das Vorhaben an den hohen Kosten zu scheitern, am 11. Mai 1888 wurde der Streckenbau aber doch beschlossen. Gut drei Jahre nach dem Bauauftrag am 16. November 1892 wurde der Abschnitt Mayen - Gerolstein am 15. Mai 1895 eröffnet.