1963 год 15 июля
Заложена на заводе "Красное Сормово" в г.Горький как КрПЛ К-58. Экипаж после формирования и стажировки подчинен 104-й ОБрСПЛ ВМФ;

1964(?) год
Переезд экипажа на сдатачную база завода "Красное Сормово" в г.Севастополь. Отработка экипажем (планировался для включения в состав ТОФ) организации службы, изучение материальной части, экслуатация материальной части на выходах в море на одной из подводных лодок проекта 651 из состава 153-й БрПЛ ЧФ;

1966 год 12 февраля
Спущена на воду;

1966 год 23 сентября
Вступила в строй;

1966 год октябрь
Зачислена в состав КСФ. После перевода на Северный флот вошла в состав 35-й ДиПЛ 1-й Краснознаменной ФлПЛ КСФ с базированием на губу Малая Лопаткина (Западная Лица, Мурманская область);

1969 год октябрь
В составе дивизии переформирована в состав 9-й ЭскПЛ КСФ с базированием на губу Ура (Видяево, Мурманская область);

1970 год декабрь - 1971 год апрель
Выполнила задачи БС (командир - Костин О.И.) на Средиземном морею. В заливе Эс-Саллум (точка 52) произвела пополнение запасов с корабля КЧФ. В походе участвовала медэкспедиция "Квартет" (для оценки состояния подводников в длительном походе). На возвращении приняла участие в учениях КСФ;

1972 год 24 октября - 1974 год апрель
На СРЗ-35 (Роста, г.Мурманск) прошла средний ремонт;

1975 год июля
Участвовала в параде кораблей на Дне ВМФ в г.Североморск;

1975 год январь - август
Выполнила задачи БС (командир - Куницкий В.С.) на Средиземном море с заходом в порт г.Тартус (Сирия) в апреле и порт г.Александрия (Египет) в августе;

1976 год - 1977 год
Выполнила задачи БС (командир - Куницкий В.С.) на Средиземном море;

1977 год 25 июля
Переименована в Б-58;

1978 год
Выполнила задачи БС (командир - Куницкий В.С.) в течении 5,5 месяцев на Средиземном море с заходом в порт г.Тартус (Сирия) для межпоходового ремонта у борта ПМ-9 и порт г.Алжир (Алжир) с дружественным визитом;

1980 год
В начале года в у пирса в Росте (г.Мурманск) произошел небольшой пожар;

1981 год 23 апреля - 1982 год 29 апреля
На СРЗ-35 (Роста, г.Мурманск) прошла капитальный ремонт;

1983 год
Выполнила задачи БС на Средиземном море с заходом в октябре в порт Тобрук (Ливия);

1990 год 19 апреля
Выведена из боевого состава ВМФ и сдана в ОФИ;

1992 год (приблизительно)
Затонула во время стоянки у пирса в губе Ура (Видяево, Мурманская область). В некоторых источниках ошибочно указано, что Б-58 прибыла на ЧФ - ПЛ только планировалась к переводу, но так и не была переведена;

2010 год
Находилась в затопленном состоянии в губе Ура под причалами на глубине до 40 м. Возможно в дальнейшем поднята и утилизирована. Однако на картах Google еще в 2020 году по координатам 69.333059, 32.886434 в воде просматривались останки ПЛ.