Bereits im Eröffnungsjahr der Bahnlinie Mauthausen - Grein waren Bestrebungen für deren Fortsetzung nach Krems a. d. Donau und damit zur Herstellung einer direkten Verbindung mit Wien im Gange. Der Wiener Bauingenieur Dr. Rudolf Mayreder brachte im April 1899 sein Projekt einer normalspurigen Lokalbahn von Krems nach Grein zur Trassenrevision und Stationskommission; die Baukosten waren auf 6 600 000 K veranschlagt.
Zu einer erfolgversprechenden Erledigung kam es jedoch erst im Jahre 1905 durch die Sicherstellungsaktion der Regierung für Lokalbahnbauten; mit einem Einzelgesetze vom 28. Juli 1905 (RGBI Nr. 123) wurde auch für die 76,5 km lange Lokalbahn Krems - Grein die gleiche Art der Staatsunterstützung wie für die Teilstrecke Mauthausen - Grein gewährt. Der Staat sicherte für ein Kapital von 15300 000 K die Erträgnisgarantie unter der Voraussetzung zu, daß die Länder Nieder- und Oberösterreich mit den Interessenten zusammen einen Beitrag von 2100000 K leisten54.
Am 14. Dezember 1905 wurde der Lokalbahn-AG Mauthausen - Grein in Wien die Konzession erteilt (RGBl Nr. 190). Ende 1907 vergab das Eisenbahnministerium den Bau an drei Bauunternehmungen, das dritte Baulos, Marbach - Grein, von dem ungefähr 8 km (ab Sarmingstein) auf oberösterreichisches Gebiet entfallen, an die Bauunternehmung Oswald Ziwotski in Prag. Anfang 1908 wurde der technisch schwierige Bau unter der Bauaufsicht des Eisenbahnministeriums begonnen; zahlreiche Überbrückungen und mehrere Tunnelierungen waren erforderlich. Die Endstrecke, 76,5 km lang, wurde Ende November 1909 vollendet und am 4. Dezember 1909 dem öffentlichen Verkehr übergeben55; der kurze oberösterreichische Streckenteil (9,1 km) von der Station Sarmingstein bis Grein (nun in "Grein-Bad Kreuzen" umbenannt) hat 2 Haltestellen.
Nach Eröffnung des durchgehenden Verkehrs ging die Betriebsführung an die neuerrichtete, der Staatsbahndirektion Wien unterstehende k. k. Betriebsleitung Krems über. Der bis 1909 nur von St. Valentin bis Grein durchgehende Zugsverkehr wurde zu einer unmittelbaren Zugsverbindung von Wien (Franz Josefs-Bahnhof) über Krems nach St. Valentin ausgestaltet. Damit war die einige der schönsten Gebiete Österreichs, den Strudengau und die Wachau erschließende "Donauuferbahn" Wirklichkeit geworden, eine zweite unmittelbare Bahnverbindung Oberösterreichs mit Wien geschaffen.
Mit 1. Jänner 1930 waren die Lokalbahnen Mauthausen - Grein und Krems - Grein Bundeseigentum geworden; sie wurden vom genannten Tage an gemäß Bundesgesetz von 1923 (BGBI Nr. 407) dem Wirtschaftskörper "Österreichische Bundesbahnen" zur treuhändigen Verwaltung und Betriebsführung (durch die Bundesbahn-Direktion Wien) übergeben.