Bereits um 1870 dachte man daran, durch das Tal der Ybbs und weiter durch das Bodingbachtal eine Bahnlinie nach Kienberg-Gaming zu bauen. Der Börsenkrach von Wien im Jahr 1873 bereitete den Plänen ein jähes Ende. In den 80er-Jahren des vorigen Jahrhunderts strebten Vertreter des Ybbstales erneut den Bau einer Nebenbahnlinie an. Sprecher der Gemeinden und Interessenten war der aus Waidhofen/Ybbs stammende NÖ Landtags- und Reichtagsabgeordnete Gottfried Jax. Zahllose Gespräche und Verhandlungen zeigten zunächst keinen Erfolg. Ja selbst die Trassenführung konnte nicht geklärt werden, bis 1893 die zähen Verhandlungen abgeschlossern werden konnten. Die Bemühungen und das Engagement der Befürworter hatte endlich Erfolg. Der Reichsrat verabschiedete noch am 26. Dezember desselben Jahres ein Gesetz für den Bau der Ybbstalbahn. Noch vor Baubeginn kam es durch einen Erlaß des Innenministeriums vom 11. Sept. 1895 zur Gründung einer Aktiengesellschaft. Das Anlagekapital betrug damals 1.612.000 Gulden.
Am 01.06.1895 erfolgte der Spatenstich für den ersten Streckenabschnitt Waidhofen – Groß-Hollenstein, beim „kleinen Kreuz” in Waidhofen. Die Eröffnung dieses Teilabschnittes fand bereits am 15. Juli 1896 statt.
Drei Jahre später, am 15. Mai 1898 kam es zur Eröffnung des zweiten Teilabschnittes von Großhollenstein bis Lunz/See. Noch im selben Jahr, am 12. November wurde das bautechnisch schwierigste dritte Teilstück von Lunz/See nach Kienberg-Gaming für den Verkehr freigegeben.
Drei Jahre dauerte das Errichten der 71 km langen Strecke. Damit wurde die projektierte Bauzeit von fünf Jahren um zwei Jahre unterschritten.
Am 9.März 1899 wurde schließlich die Stichbahn von Gstadt nach Ybbsitz mit einer Länge von 6 km eröffnet.
In ihrer über 110-jährigen Geschichte konnte die Ybbstalbahn alle Kriegszeiten, Hochwässern und Einstellungsversuche überstehen. Erst die vom Land NÖ und einigen Anrainergemeinden forcierten Pläne zur Errichtung eines Radwegs auf der Bahntrasse brachten in Verbindung mit dringend notwendigem Sanierungsaufwand für einen Teil der Strecke und dem mangelnden Engagement des vormaligen Besitzers ÖBB das Ende der Strecke. Geringfügige Unwetterschäden im Juni 2009 wurden nicht mehr repariert und der Verkehr auf den kurzen Abschnitt von Waidhofen bis Gstadt reduziert. Trotz massiver Proteste wurde die Strecke im Laufe des Jahres 2014 zwischen Göstling und Gstadt abgetragen.