Die Bahnstrecke ist eine der ältesten Bahnverbindungen in der Region. Der östliche Teil lag damals im Russischen Kaiserreich, während der westliche ein Teil des österreichischen Galizien war. Die Strecke zwischen Odessa und Podilsk wurde 1865 durch die Odessa-Parkany Eisenbahn, später ein Teil der Odessaer Eisenbahnen, eröffnet. 1870 folgte dann der Weiterbau der Strecke von Schmerynka nach Podilsk durch die Kiew-Baltaer Eisenbahn, 1871 dann noch die Verlängerung über Chmelnyzkyj nach Wolotschysk an die damalige russische Grenze durch die Kiew-Brester Eisenbahn.[1]
Der im damaligen Galizien gelegene Teil der Bahn wurde in mehreren Schritten durch die Galizische Carl Ludwig-Bahn eröffnet. Die als Zweigstrecke zur Bahn nach Brody erbaute Linie Krasne–Złoczów wurde am 12.Juli 1869 eröffnet, am 22.Dezember 1870 folgte die Verbindung Złoczów–Tarnopol und am 4.Oktober 1871 die Reststrecke Tarnopol–Podwołoczyska mit Anbindung an das russische Netz. Da die Galizische Carl Ludwig-Bahn in der in Österreich üblichen Normalspur erbaut wurde, konnten keine durchgehenden Zugläufe erfolgen. Handelswaren mussten deshalb in Pidwolotschysk umgeladen werden und Reisende umsteigen. Ein großer Umlade- und Umsteigebahnhof entstand. Die Konzessionierung der Strecke erfolgte bereits am 15.Mai 1867[2].
Die Zweigstrecke nach Hrymajliw wurde erst am 12.August 1897 als Lokalbahn Borki Wielkie–Grzymałów eröffnet, die Betriebsführung wurde von der Österreichischen Staatsbahn übernommen. Die Konzessionierung dieser Lokalbahnstrecke erfolgte bereits am 23.März 1896.[3] Die Lokalbahn bestand in ihrer eigenständigen Form bis 1932, als sie durch die Polnischen Staatsbahnen übernommen wurde.[4]
Nach dem Ende des Ersten Weltkrieges kam der westliche Teil der Bahn bis Pidwolotschysk/Wolotschysk zu den Polnischen Staatsbahnen, der östliche Teil ging an die Sowjetische Eisenbahn. Die Direktverbindung nach Russland wurde unterbrochen, der Verkehr endete an der Grenzstation.
Durch die Besetzung Ostpolens durch die Sowjetunion kurz vor dem Beginn des Zweiten Weltkrieges 1939 kam der westliche Teil der Strecke auch in den Besitz der Sowjetischen Eisenbahnen, diese begannen sofort mit der Umspurung einzelner Strecken auf Russische Breitspur (1520mm), dies wurde aber nach dem Überfall Deutschlands auf die Sowjetunion 1941 rückgängig gemacht und die Strecken der Ostbahn unterstellt. Die Strecke Lemberg—Krasne—Tarnopol—Podwoloczyska bekam die Nummer 535.[5], gleichzeitig wurde auf der bisher eingleisigen Strecke aus strategischen Gründen ein 2. Gleis verlegt.
Nach dem Ende des Krieges wurde die Strecke wieder durch die Sowjetischen Bahnen in Besitz genommen, diese spurte die gesamte Strecke wieder auf Breitspur zurück und gliederte sie in ihr Netz ein, dieses wurde 1991 durch die Ukrainischen Bahnen übernommen.
Durch die Aufwertung der Verbindung nach Lemberg wurde der Abschnitt Krasne-Ternopil-Chmelnyzkyj-Schmerynka-Wapnjarka zwischen 1995 und 1998 vollständig elektrifiziert. Bereits 1989 erfolgte die Elektrifizierung der Verbindung von Odessa nach Wapnjarka.