The origins of the lines traversed by route 58 lies in separate tram lines. 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 of track between Park Street, South Yarra (near Stop 123) and Chapel Street (Stop 128) was built later that year on 26 October as part of the Prahran cable tram line. 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. Meanwhile, the line between Collins Street (Stop 4) and Daly Street, Brunswick West (Stop 33) was constructed by the MMTB on 19 July 1925. This section was extended to West Coburg on 26 June 1927. The line between Sturt Street (Stop 118) and St Kilda Road was constructed on 27 December 1925. The line connecting Collins Street and Sturt Street finally opened on 21 December 1944. From 1 July 2017, route 58 was rerouted via Toorak Road West with the closure of Domain Road while Anzac railway station was built.[4][5]
During 2021, tram stop upgrades along the route were undertaken to allow the introduction of E class trams on the route, which commenced operation on 19 December 2021.[6][7][8][9] These replaced D1 class trams from Malvern.[10]