- 1995年12月：58線開辦，初時經蒲飛路、薄扶林道、沙宣道同域多利道（碧瑤灣）。
- 1996年2月16號：配合中華巴士77線（香港仔←→西環荷蘭街）取消，改經域多利道（摩星嶺段）同大口環道。
- 1998年5月：配合田灣邨重建入伙，來回程經田灣邨。
- 2003年10月23號：路線重組，唔再經田灣邨。
- 2005年9月11號：來回程改經數碼港道，唔再經碧瑤灣一段域多利道，改係開辦經碧瑤灣嘅特別班次取代，初時只喺禮拜一到五10:00-16:00提供服務。同年10月23號起特別班次命名係58A。
- 2008年2月24號：調整收費，全程收費由HK$4.8調整到HK$5，而部份分段收費由HK$2–$3.7調整到HK$2.2-$3.8。
- 2011年2月27號：推出同4A，4B，4C往返石排灣，63往返海怡半島，以同4S，39C，39S，51S，59A，63A轉乘呢條線（或相反）嘅八達通轉乘優惠。
- 2011年11月28號：調整收費，全程收費由HK$5調整到HK$5.4，而部份分段收費由HK$3.8–$4調整到HK$4-$4.3。
- 2013年6月16號：調整收費，全程收費由HK$5.4調整到HK$5.9，而分段收費由HK$2.2–$4.3調整到HK$2.5-$4.5。
- 2014年11月30號：調整收費，全程收費由HK$5.9調整到HK$6.5，而分段收費由HK$2.5–$4.5調整到HK$2.8-$5.1。
- 2014年12月25號：配合西港島綫將喺同年12月28號投入服務，呢條線同59線遷移到堅尼地城站專綫小巴上落客區。[4]
- 2014年12月28號：呢條線新增同港鐵堅尼地城站嘅八達通轉乘優惠，成人次程可減收HK$0.5；翌號新增58M(貝沙灣(南灣)－堅尼地城站)，係58線嘅區間車，只喺禮拜一到五早上到黃昏提供服務。[5]
- 2015年10月18號：58系列路線堅尼地城端嘅總站由北街遷往堅尼地城站，唔再途經爹核士街、堅彌地城新海旁、山市街、卑路乍街、北街同石山街，改係直接途經士美菲路南行直接前往總站，以配合堅彌地城新海旁喺士美菲路同北街嘅間改係單向西行。
小巴58線路線圖同埋停站位置
- 58
- 58A
- 58M
- 58、58A↔51：由呢個路線往香港仔方向喺上車後1小時內轉乘51線，次程車費減$1；由51線轉乘呢個路線往堅尼地城方向，兩程車費合共HK$6.2。
- 58、58A↔4A、4B、4C、5、35M：由呢個路線往香港仔方向喺上車後1小時內轉乘上述路線往銅鑼灣/灣仔方向，或由上述路線往石排灣方向轉乘呢個路線往堅尼地城方向，次程可獲HK$1優惠。
- 58、58A↔4A、4B、4C往返石排灣、4S、39C，39S，51S，59A，63，63A：由呢個路線上車後1小時內轉乘上述路線往南區各屋苑或海怡半島方向，或由上述路線往香港仔方向轉乘呢個路線往堅尼地城方向，次程可獲HK$1嘅折扣優惠，但4A、4B同4C線只適用喺HK$2.2或以下嘅分段收費。
- 58/58M↔港鐵：由呢個路線往堅尼地城方向上車後1小時內喺堅尼地城站轉乘港鐵，或由堅尼地城站出閘後1小時內轉乘呢個路線往香港仔／數碼港方向，第二程可獲HK$0.5嘅折扣優惠，優惠只適用成人八達通。
呢個系列路線（包括58、58A、58M、59、59A同59B線）字軌有28部車，包括豐田Coaster同三菱Fuso Rosa。
- 喺平號上午同下午繁忙時間，呢個系列路線26部車嘅中，其中3部會分別調動到51同51S線
皆因58線係來往香港仔到堅尼地城嘅唯一交通工具，而亦有前往數碼港上班嘅乘客支持，所以有一定嘅客流量。
