Обеспечивать их действия должны были два крейсера и четыре эсминца, но затем, поскольку пребывание советских войск на Кубе считалось государственной и военной тайной, от их развёртывания отказались — ради сохранения конспирации. Ракетоносцы не смогли сразу отправиться в дальний поход, 1 октября в Карибское море ушли всего лишь четыре дизельные торпедные лодки проекта 641. Это были Б-4 (капитан 2 ранга Р. А. Кетов), Б-36 (капитан 2 ранга А. Ф. Дубивко), Б-59 (капитан 2 ранга В. Г. Савицкий) и Б-130 (капитан 3 ранга Н. А. Шумков). Отряд возглавил командир 69-й бригады подводных лодок капитан 1-го ранга В. Н. Агафонов, находившийся на борту Б-4.
Подводная лодка пр. 641
Район назначения командиры лодок узнали только в океане после вскрытия секретных пакетов, однако выполнить поставленную задачу они не смогли. Ещё на подходе, в районе Багамских островов, советские лодки были обнаружены противолодочными силами ВМФ США, осуществлявшими морскую блокаду Кубы и организовавшими длительное преследование. В результате, полностью разрядив аккумуляторные батареи, три советские лодки одна за другой всплыли на поверхность моря неподалеку от американских кораблей. Уйти от американцев смогла только одна лодка Б-4.
В Москве весьма болезненно восприняли провал подводного рейда к Кубе. После возвращения лодок на базу был устроен показательный «разбор полётов» под руководством первого заместителя министра обороны СССР маршала А. А. Гречко. Для начала он заявил: «я предпочёл бы утонуть, а не всплывать».
Но в ходе заседания неожиданно выяснилось, что как министр, так и другие руководители Минобороны были уверены в том, что в Карибское море ходили атомные подводные лодки. Видимо, слишком часто и слишком настойчиво командование ВМФ рекламировало их огромные боевые возможности. Однако когда дошло до дела, оказалось, что «чудо-оружие» советского флота не пригодно для океанских боевых походов — настолько ненадёжны их энергетические установки.
Уяснив сей прискорбный факт, маршал Гречко прекратил дальнейшее разбирательство — экипажи дизельных лодок сделали всё, что могли и даже больше того. Стало совершенно ясно, что отечественные дизель-электрические лодки для дальних океанских походов не годятся (в отличие от их прототипа, германских субмарин XXI серии).
В первой половине 60-х годов в океан стали, наконец, выходить и первые атомоходы. В 1961 году пробный 14-суточный поход в Северную Атлантику совершила К-52, через год подлодка К-21, которой командовал будущий главком ВМФ СССР Чернавин, провела в море 51 сутки, пройдя под водой около 9000 миль. В том же году головная лодка проекта 627 К-3 прошла в подводном положении Северный полюс, осваивая просторы Северного Ледовитого океана. Вскоре подводная лодка К-115 капитана 2-го ранга И. Дубяги совершила трансарктический переход под льдами из Баренцева моря в Тихий океан.
Затем настал черёд освоения Атлантики, куда отправилась К-33. Экипаж капитана 2-го ранга Г. Слюсарева пересёк экватор, сумев справиться с серьёзной аварией — в подводном положении произошел разрыв первого контура реактора. Символом мощи советского подводного флота стало кругосветное групповое плавание атомных подводных лодок, о котором сообщила вся советская печать. Ещё бы, ведь это был подарок военных моряков XXIII съезду КПСС! Правда, при этом забыли упомянуть то обстоятельство, что назвать его кругосветным можно только с натяжкой. В действительности подводные лодки К-133 и К-116 совершили переход с Северного флота на Тихоокеанский через Атлантический океан, пролив Дрейка и Тихий океаны.
С 1964 года корабли ВМФ СССР приступили к регулярному несению боевой службы, главными задачами которой считались постоянное патрулирование ракетных подводных крейсеров стратегического назначения в постоянной готовности к нанесению удара по наземным объектам, поиск и слежение за ракетными подводными лодками и авианосными соединениями вероятного противника.
При этом подводные ракетоносцы первого поколения, в силу малой дальности действия ракетных комплексов, были вынуждены действовать в непосредственной близости от берегов стран НАТО, где постоянно находились в зоне пристального внимания противолодочных сил противника.
Обеспокоенные быстрым наращиванием советского подводного флота, американцы предпринимали большие усилия по противодействию подводной угрозе. В море постоянно находилось до 6—7 авианосных многоцелевых групп, несколько десятков подводных лодок, действовали значительные силы противолодочных кораблей и авиации, началось развёртывание стационарной системы подводного обнаружения SOSUS, многочисленных станций радиоэлектронной разведки. Особую опасность для советских подводных лодок представлял Фареро-Исландский противолодочный рубеж, при преодолении которого чаще всего происходило их обнаружение силами вероятного противника. Но уже ничто не могло остановить советские субмарины.