С вышедшего в море, несмотря на непогоду, спасательного судна «Алдан» пытались спустить батисферу, но из этого ничего не получилось. Помешал начавшийся шторм. Вскоре ветер достигал уже десяти баллов, а волнение моря — семи. Командующий флотом отдал приказ всем задействованным в поиске кораблям и судам укрыться от шторма за островом Кильдин. В море остались лишь эскадренный миноносец «Сведущий» под флагом командующего и спасательное судно «Алдан». Когда погода немного улучшилась, поиск немедленно продолжили.

Интенсивная поисковая операция производилась вплоть до 16 февраля, но оказалась безрезультатной. Расчетное время возможного существования людей на борту затонувшей лодки истекло. Поисковые работы начали было уже понемногу свертывать, когда 2 марта спасательное судно СС-21 зацепилось якорем за неизвестный тяжелый предмет, лежащий на дне. Предмет этот оставил на лапе якоря след сурика, которым окрашивали корпуса подводных лодок. Снова последовали серия выходов в море и тщательное обследование «подозрительного» района, но и здесь все оказалось напрасным. Пропавшей субмарины не нашли. Как показали расчеты, к этому времени даже при самом благоприятном развитии ситуации для оказавшихся в подводном плену моряков С-80 из них никто уже не мог остаться в живых. В связи с этим было решено больше не изматывать понапрасну экипажи кораблей и судов, а вернуть их в свои базы. Однако поисковые мероприятия продолжались еще вплоть до августа 1961 года кораблями различных соединений по специально разработанному плану штаба Северного флота.

Год за годом корабли в какой уже раз обследовали район предполагаемой гибели С-80. Один раз был даже обнаружен лежащий на глубине двухсот сорока метров неизвестный танкер. С новой силой работы возобновились в 1965 году. При этом использовалась вся новейшая аппаратура: гидрографические эхолоты, магнитные металлоискатели, специальные гидрологические станции поиска затонувших подводных лодок и телевизионные подводные установки. Так, по плану в 1967 году корабли производили поиск в южной части района, а в следующем, 1968-м, перешли в северную. Настойчивость и последовательность североморцев оказались в конце концов вознаграждены.

23 июля спасательное судно СС-47 в северо-восточной части полигона, где пропала С-80, в точке с координатами: широта 70 градусов 01 минута 23 секунды северная, долгота 35 градусов 35 минут 22 секунды восточная на глубине 196 метров с помощью гидролокационной станции поиска затонувших подводных лодок МГА-6 обнаружило затонувшую подводную лодку.

Первое же визуальное обследование, произведенное с 12 по 20 августа наблюдательными камерами НК-300 и НК-600, показало, что затонувшая подводная лодка и есть пропавшая в 1961 году С-80. Осматривать затонувшую лодку спускался на наблюдательной камере лично первый заместитель командующего Северным флотом вице-адмирал А. И. Петелин. В свете прожектора субмарина являла собой фантастическое и жуткое зрелище.

20 августа специалисты по результатам наружного обследования и исходя из внешнего вида подводной лодки сформулировали общую версию гибели С-80. Лодка лежала на грунте без дифферента с креном в 35 градусов на правый борт. Носовая часть слегка задрана вверх. Корпус субмарины был сильно опутан рыбацкими сетями и поплавками. Оба аварийных буя были отданы. РДП, антенны и ВАН подняты в верхнее крайнее положение. Обрастание ракушками и водорослями незначительное. Предварительный вывод сводился к следующему: ракетоносец шел на перископной глубине в режиме РДП, то есть при работающих дизелях, а затем по какой-то причине резко устремился вниз. Возможно, что командир внезапно увидел неизвестное судно, шедшее на опасное сближение, и скомандовал «срочное погружение». Поплавковый клапан при этом обледенел и не сработал — вода хлынула в отсеки. Экипаж пытался «продуться» и всплыть, но тщетно. Лодка легла на грунт. Некоторое время люди были еще живы, об этом говорили оба выпущенных аварийных буя.

Позднее Государственная комиссия определит причины, почему так долго продолжался поиск пропавшей подводной лодки:

— несовершенство поисковой аппаратуры;

— организация основного поиска в южном районе полигона, там, где был обнаружен аварийный буй.

Получив доклад об обнаружении С-80, Главнокомандующий ВМФ отдал приказ поднять подводную лодку не позднее лета 1969 года. В связи с этим была сформирована специальная экспедиция ЭОН-10. Командиром назначен опытный спасатель капитан 1-го ранга С. В. Минченко. Сама же операция по подъему С-80 получила кодовое название «Глубина».

Уже в апреле 1969 года на Черном море были проведены учения по подъему подводной лодки с грунта, в ходе которых выяснилось, что для успешного подъема с большой глубины необходима надежная амортизация подъемных устройств. Такие устройства были в срочном порядке разработаны и изготовлены из особо прочных капроновых тросов.

Первоначально для подъема предполагалось использовать специальное захватывающее устройство, которое срочно начали изготавливать на горьковском заводе «Красное Сормово». Однако затем в силу ряда причин этот проект был пересмотрен и принято решение поднимать С-80 с помощью специальных металлических полотенец.

3 мая 1969 года к месту трагедии направились три корабля экспедиции. Операция «Глубина» началась. Первым делом корабли, прибыв в расчетную точку, над местом гибели лодки выставили ограждение из шести рейдовых бочек. Затем в центр этого ограждения вошло новейшее спасательное судно «Карпаты» водоизмещением в 10 тысяч тонн. Оно имело два 750-тонных подъемника, работающих как раздельно, так и в паре, а кроме того, по одному подъемнику в 100 и 60 тонн и два по 10. Именно «Карпатам» отводилась главная роль в начинающихся работах.

Непосредственно же работы по подъему подводной лодки начались 9 июня 1969 года. Вначале подводную лодку очистили от сетей. Затем под ее нос и корму подвели специальные, соединенные с гинями металлические полотенца. Операцию затрудняли постоянная зыбь, неустойчивая погода и малая прозрачность воды, вызванная цветением планктона. Проводимым работам постоянно мешало и разведывательное норвежское судно «Мариетта», которое в своем стремлении выяснить, что же делают русские, маневрировало слишком близко. Норвежцев несколько раз предупредили, однако действия это не возымело. Пришлось разведывательное судно достаточно бесцеремонно вытеснять из района. Помимо назойливой «Мариетты» то и дело появлялись невесть откуда взявшиеся английские траулеры. В воздухе непрерывно патрулировали самолеты «Нептун». Вероятный противник по холодной войне никак не мог уяснить суть проводимых работ, а потому нервничал. Но, несмотря ни на что, операция по подъему подводной лодки продолжалась круглосуточно.

После того как под корпус С-80 завели полотенца и стропы, их закрепили, несколько дней пережидали внезапный шторм. Едва он стих, начали подъем. Мощные подъемники «Карпат» медленно оторвали С-80 от грунта, и она как бы повисла на тросах.

К 10 июля лодку удалось поднять на 110 метров. Затем «Карпаты» дали самый малый ход вперед, и вся флотилия спасателей осторожно двинулась к берегу. Впереди шли два тральщика, прощупывая гидроакустическими станциями и эхотралами дно. Еще два тральщика прикрывали «Карпаты» слева и справа. Самим же «Карпатам» помогали двигаться на буксире спасатель СС-44 и морской буксир СБ-155. Еще несколько небольших судов подстраховывали их на случай обрыва троса. Скорость всей флотилии не превышала двух с половиной узлов. На больших ходах гини начинали опасно вибрировать и могли не выдержать нагрузки. Движение было скрытным. Очень кстати оказался внезапный сильный туман, позволивший нашим спасателям незаметно для натовского разведсудна уйти из полигона. Когда же туман рассеялся и «Мариетта» вернулась в район спасательных работ, то там уже никого не было. Раздосадованные натовцы принялись палить из крупнокалиберного пулемета по оставшемуся на месте боковому заграждению.