Progress M-58 was launched by a Soyuz-U carrier rocket from Site 1/5 at the Baikonur Cosmodrome. Launch occurred at 13:40:36 GMT on 23 October 2006. The spacecraft docked with the Aft port of the Zvezda module at 14:28:46 GMT on 26 October. During docking a problem with the spacecraft's telemetry system produced a false reading that an antenna associated with its Kurs docking system had failed to retract, complicating the docking procedure. It remained docked for five months before undocking at 18:11 GMT on 27 March 2007. It was deorbited at 22:44:30 GMT on 27 March 2007. The spacecraft burned up in the atmosphere over the Pacific Ocean, with any remaining debris landing in the ocean at around 23:30:22 GMT.
Progress M-58 carried supplies to the International Space Station, including food, water and oxygen for the crew and equipment for conducting scientific research.
Payloads are separated by bullets ( · ), launches by pipes ( | ). Manned flights are indicated in bold text. Uncatalogued launch failures are listed in italics. Payloads deployed from other spacecraft are denoted in brackets.