Как бы там ни было, но в декабре 1960 года обе лодки с ракетным комплексом уже вступили в первую линию. Как свидетельствуют документы С-80, по своему техническому состоянию и по уровню подготовки экипажа она была вполне готова для выполнения задач в море.
Из воспоминаний Героя Советского Союза адмирала флота Г. М. Егорова, бывшего в то время командиром дивизии, куда входила С-80: «Подводные лодки с крылатыми ракетами — новые, сложные по устройству и управлению корабли. Поэтому нам часто приходилось выходить в море, изучать личный состав, особенно командиров кораблей. Тогда-то я и обратил внимание на одного из командиров. В море он допускал оплошности, часто нервничал, что совершенно недопустимо для подводника. Я не раз обращался и к командующему подводными силами контр-адмиралу Г. Т. Кудряшову, и к командующему флотом адмиралу А. Т. Чабаненко с просьбой направить этого командира на тщательную медицинскую проверку, но этого сделано не было. Вскоре я снова вышел в море на той же подводной лодке для проверки корабля и всех его систем на глубоководное погружение с уходом на рабочую глубину до 170 метров. Испытание показало, что прочный корпус корабля, все забортные отверстия, механизмы, в основном, удовлетворяли предъявляемым требованиям. Но снова возникли серьезные претензии к командиру корабля. Поэтому, возвратившись с моря, я приказал начальнику штаба дивизии капитану 1-го ранга Н. М. Баранову не отправлять лодку в море, а заняться совершенствованием подготовки командира и личного состава непосредственно в базе. Вскоре я убыл в очередное плавание со всем соединением. Там, в море, по перехваченным радиограммам узнал, что подводная лодка С-80 по приказанию штаба подводных сил отправлена в море на отработку задач боевой подготовки. Не раздумывая, решил, что допущена серьезная ошибка. Поэтому, не вступая в полемику, а ссылаясь на тяжелый прогноз погоды, немедленно дал радиограмму в штаб подводных сил: „В связи с приближающимся ураганом, прошу ПЛ С-80 срочно возвратить в базу“».
Итак, 25 января ракетная подводная лодка С-8 °Cеверного флота покинула базу и прибыла в полигон боевой подготовки в 50 милях севернее бухты Тириберка для отработки задач К-2. На выходе в море ей предстояло определить возможность плавания в подводном положении под одним электромотором на малых оборотах, при благоприятной погоде опробовать зарядку аккумуляторов под РДП и обучить вновь прибывших на лодку молодых матросов. На борту в тот момент находились 68 человек: 15 офицеров, 16 старшин и 37 матросов, из них прикомандированными на выход в море с других экипажей были 2 офицера и 7 матросов.
27 января в 0 часов 47 минут С-80 донесла о своем нахождении в районе и передала сведения о состоянии погоды. Согласно плану, подводная лодка должна была до 18 часов 00 минут из-за резкого ухудшения погоды покинуть полигон, о чем ей надлежало донести в штаб подводных сил Северного флота.
Из воспоминаний Героя Советского Союза адмирала флота Г. М. Егорова: «Приближение шторма чувствовалось по многим признакам. Резко падало давление барометра. Крепчал ветер, меняя направление с южного на северный. Это сулило сильный шторм. Я приказал часть лодок с рейда отправить в море, погрузиться на глубину в назначенных районах. К трем часам ночи шторм вроде ослабел. Но вскоре налетел шквалистый северный ветер со снежными зарядами и, как разъяренный зверь, накинулся на корабли. Находясь на мостике плавбазы „Иртыш“, которую на якорях носило с борта на борт усилившимся до ураганной силы ветром (25–30 метров в секунду при сплошных снежных зарядах), я следил по локации за состоянием кораблей на рейде. От командиров лодок периодически поступали доклады о положении дел. Пришла радиограмма от подводной лодки С-80. Поскольку она была адресована штабу подводных сил, мы не смогли ее раскодировать. Полагал, что моя просьба выполнена и командир С-80 подтвердил приказание штаба о возвращении, лодка направляется в базу. К тому же порядок работы связи запрещал мне с моря давать лишние запросы. Заканчивалась штормовая полярная ночь. Начало светать. Теперь, казалось, можно успокоиться. Но вдруг получаю тревожный доклад: „Узел связи флота постоянно вызывает подводную лодку С-80. Ответа от нее нет“. Мое беспокойство за корабль и экипаж вновь возросло. С ураганом шутки плохи. Каких только не возникло тогда предположений о причинах молчания корабля. Поначалу думал, что отказала связь. Мысли крутились и вокруг возможности погружения лодки. Командир С-80, не получив распоряжения штаба подводных сил о возвращении в базу, мог пойти на это, чтобы укрыться под водой от шторма. В тяжком ожидании прошел день, ветер почти успокоился, а подводная лодка все молчала. По приказу командующего флотом рейдовый сбор нашего соединения был прекращен. Лодки возвратились в базу. Прямо с причала меня вызвали в штаб флота».
Обеспокоенный надвигающимся штормом, штаб подводных сил передал командиру лодки приказ возвращаться в базу, однако квитанции не получил. Эфир, несмотря на все последующие многочисленные запросы, был пуст. Никому не хотелось верить в худшее. По флоту была немедленно объявлена боевая тревога. Сравнивая ситуацию с исчезновением С-80, нельзя не поразиться ее почти полной схожести с исчезновением С-117. Не менее схоже развивались события и далее.
28 января командующий Северным флотом отдал приказ на начало поисковой операции. В море немедленно вышли эскадренные миноносцы «Гремящий» и «Оживленный», подводные лодки С-46 и Б-36, четыре малых противолодочных корабля, вылетели два самолета Бе-6. Что касается подводной лодки С-46, то она, как и пропавшая без вести С-80, относилась к проекту 644. Перед самым выходом в море командир бригады, который должен был быть старшим на борту, и командир лодки выходить на ней в море наотрез отказались. Оба были немедленно заменены, а затем и сняты со своих должностей. Почему отказались идти в море два достаточно опытных подводника, ведь они прекрасно понимали, что этого отказа им не простят? Скорее всего, дело было в неверии в лодки 644-го проекта, которое после исчезновения С-80 и вызвало такую реакцию. Здесь возникает вопрос: почему командование Северным флотом решило отправить в море именно С-46, когда в готовности к выходу имелось и немало иных лодок? Возможно, такой выбор обусловлен желанием посмотреть на поведение лодки 644-го проекта в море в различных режимах плавания, чтобы попытаться смоделировать ситуацию на С-80; возможно, этот выбор был продиктован стремлением преодолеть у экипажа С-46 естественный психологический барьер, появившийся после гибели «систершипа» их субмарины, а возможно, направили в море то, что оказалось ближе под рукой…
Несмотря на все усилия, в районе поиска никаких следов аварии или катастрофы не обнаружили. Поисковые силы, однако, непрерывно наращивались и к середине дня уже насчитывали пять эсминцев, шесть подводных лодок, восемь малых противолодочных кораблей, три тральщика, восемь самолетов Бе-6, семь вертолетов Ми-7 и восемь спасательных судов.
При этом все участвующие в поиске силы были разделены на семь отрядов. 1-й отряд составили эскадренные миноносцы: «Сведущий», «Скромный», «Настойчивый», 2-й отряд — «Гремящий» и «Оживленный», 3-й — подводные лодки, 4-й и 5-й — ПУГи малых противолодочных кораблей, 6-й — тральщики, а 7-й — спасательные суда. В отдельные отряды объединили самолеты и вертолеты. Отряд обеспечения составили танкеры и торпедные катера. Район поиска непрерывно расширялся. Одновременно проводился опрос экипажей всех проходивших мимо района предполагаемой гибели С-80 судов.