Route 58 was introduced on 1 May 2017 as part of a restructure of the Yarra Trams network to facilitate the closure of Domain Interchange and the construction of Anzac railway station.

The oldest section of track belongs to the section between Domain Interchange (near Stop 119) and Toorak Road (Stop 22), which dates back to the Brighton Road cable tram line, which opened on 11 October 1888.

The section between Chapel Street and Orrong Road (Stop 134) was built as the Toorak cable tram line, which opened on 15 February 1889.

This section was extended by the Melbourne & Metropolitan Tramways Board (MMTB) to Glenferrie Road (Stop 139) on 8 May 1927.

The line between Sturt Street (Stop 118) and St Kilda Road was constructed on 27 December 1925.