Заложена 25 октября 1937 года на заводе № 112 (Красное Сормово) в Горьком под стапельным номером 251. 28 апреля 1939 года подводная лодка спущена на воду. Вскоре она была погружена на железнодорожный транспортер и направлена на завод № 198 в Николаев, где вступила в строй и 10 октября 1939 года под командованием Керна Акима Алексеевича вошла в состав Черноморского флота.

    22 июня 1941 года «М-58» встретила подкомандованием капитан-лейтенанта Елисеева Николая Васильевича в составе 7-го дивизиона 2-й бригады ПЛ ЧФ в Севастополе. Незадолго до начала войны субмарина завершила на севастопольском заводе № 201 гарантийный ремонт и находилась в оргпериоде. В июле 1941 года «М-58» дважды выходила в дозор в район юго-западнее мыса Тарханкут (позиция № 1) и северо-восточнее о Фидониси (позиция № 6), но противника не встретила.

    В августе-сентябре подводная лодка патрулировала в районе юго-восточнее Одессы (позиция № 7), у Сулины (позиция № 17) и близ Констанцы (позиция № 11). Противник встречен не был. 30 сентября и 1 октября за кормой субмарины гремели взрывы мин, но подлодка повреждений не получила.

    16 октября 1941 года «М-58» вышла в свой шестой боевой поход в район Констанцы (позиция № 11), из которого не вернулась. Вместе с кораблем погиб 21 подводник.

    Вероятно, «М-58» погибла на мине в период с 17 по 21 октября 1941 года. Версия о том, что субмарина стала жертвой атаки болгарского гидросамолета «Врана» («Шмолек S.328») в районе мыса Шабла днем 15 октября 1941 года не соответствует действительности, так как в этот момент подлодка находилась в базе. По некоторым данным корпус субмарины обнаружен на грунте.