The first 1,600 mm (5 ft 3 in) line to be built from Victoria into New South Wales was the Deniliquin - Moama line. Permission was granted to the private Deniliquin and Moama Railway Company by the New South Wales Government in 1874 to construct a 72 kilometres (45 mi) long line from Moama on the Murray River north to Deniliquin, connecting with the Victorian railway system at the Murray Bridge, near Echuca. Opened in 1876, it was later purchased by Victorian Railways.
In 1904 when the Victorian Parliament authorised an extension of the Goulburn Valley line 13.2 kilometres (8.2 mi) north from Strathmerton station, to the south bank of the Murray River across from Tocumwal. The line was opened in February 1905, and in April 1906 the two state Premiers (Thomas Bent and Joseph Carruthers) signed an agreement for a final 3.3 kilometres (2.1 mi) extension, into the town itself. The existing road bridge was strengthened and became the responsibility of Victoria, with both states sharing construction costs for the line. Opened in 1908, the profit (or loss) of operating the line would be Victoria's. In the station became a break-of-gauge in 1914 with extension of the NSWGR Tocumwal line.
As a result of the predicament of border towns, the Border Railways Commission (made up of representatives of both states) recommended in 1917 in favour of the construction of four additional lines into New South Wales. The most important line was to run from Swan Hill to Balranald. The culmination was the 1922 Border Railways Acts of both states, with the first outcome being that Victorian Railways took over the Deniliquin and Moama Railway Company in 1923 at a cost of £165,000. The actual construction differed from that initially proposed.
Schedule 1 to the Border Railways Act 1922 also provided that two engineers, one of whom shall be appointed by the Government of New South Wales and one by the Victorian Government, shall recommend the sites of two bridges to be constructed between a point 3 miles upstream from Mildura Wharf and downstream to a point near the Wentworth Township. The bridges were to provide for both road and rail traffic. Suitable bridges were built at both Mildura and Yelta, but no railway lines were built.