Первый опыт базирования ВМФ СССР за рубежом был приобретен, когда он располагал базами в КНР (Порт-Артур, Дальний), Польше (Свиноустье) и Финляндии (Порккала-Удд). На Балтике владение базами на территории иностранных государств существенного влияния на оперативный потенциал БФ не оказывало. На Дальнем Востоке ситуация была несколько иной, однако и здесь планирование применения сил флота ограничивалось акваторией прибрежных морей. В середине 1950-х по политическим и экономическим соображениям Советский Союз отказался от этих военно-морских баз.

В 1958–1960 годах СССР располагал военно-морской базой в Албании, в заливе Влера (бухта Паши-Лиман), где базировалась отдельная бригада подводных лодок в составе 10–12 единиц, оперативно подчиненная командующему Черноморским флотом. Благодаря наличию этой базы в 1960 году советский Военно-Морской Флот впервые провел в Средиземном море двустороннее оперативно-тактическое учение, в котором участвовали крейсер (на котором был развернут запасной командный пункт Черноморского флота), 2 эсминца и 5 подводных лодок. Однако разрыв дружественных отношений с Албанской Народной Республикой привел к потере этой базы, которая могла сыграть важную роль во всестороннем обеспечении военно-морской деятельности Советского государства в Средиземноморье.

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

В последующем все-таки были найдены пути развития системы маневренного базирования. Так, в сентябре 1970-го с правительством Объединенной Арабской Республики было заключено подготовленное в Министерстве обороны СССР соглашение об организации пункта стоянки в восточной части бухты Мерса-Матрух и с необходимыми сооружениями для материально-технического обеспечения советских военных кораблей с одновременным нахождением в ней до 5 боевых кораблей и 3 вспомогательных судов. Соглашением также предусматривалось строительство домов гостиничного типа (пансионатов) в городах Александрия и Мерса-Матрух для размещения офицеров с семьями и сверхсрочнослужащих ВМФ СССР. Аренда их предусматривалась сроком на 25 лет.

В 1970–1980-х годах организация материально-технического обеспечения сил боевой службы постоянно совершенствовалась. Принципиально новым шагом стало создание пунктов материально-технического обеспечения (ПМТО). Их организация предусматривала пополнение материальных запасов кораблей со специально созданных на территории иностранных государств складов, а также производство ремонта с использованием размещенных в этих пунктах советских плавмастерских и плавдоков.

На побережье Атлантического океана ПМТО создавались в Конакри (Гвинея), Сьенфуэгос (Куба), Луанда (Ангола), а в Индийском океане – на острове Дахлак (Эфиопия). В Средиземном море советским ВМФ использовались ПМТО в Мерса-Матрух и Порт-Саиде (Египет), Тартусе и Латакии (Сирия). Кроме того, для пополнения запасов и проведения текущего ремонта кораблей в различные периоды использовались порты Александрия (Египет), Сплит и Тиват (Югославия), Бизерта и Сфакс (Тунис), Триполи и Тобрук (Ливия) и остров Сирос (Греция). На западном и восточном побережьях Африки советские корабли получили возможность заходить в порты Гвинеи (1971 год), Сомали (1972 год), Бенина (1977 год), Республики Сан-Томе
и Принсипи (1978 год). Разведывательные и противолодочные самолеты ВМФ использовали аэродромы Египта, Алжира, Кубы, Гвинеи, Народной Демократической Республики Йемен
и Вьетнама, где были развернуты авиационные комендатуры. Работавшие на Кубе, в Адене
и Камрани (Вьетнам) подвижные узлы связи в значительной степени увеличивали возможности управления силами боевой службы в удаленных районах Мирового океана. Одновременно наращивался потенциал плавучего тыла. К концу 1970-х он располагал уже 38 судами тоннажем 332 тыс. т. Однако за первые 10 лет боевой службы проблему формирования развитой системы пунктов базирования на территории зарубежных государств окончательно решить не удалось,
в первую очередь – из-за слабого суверенитета «друзей СССР» в Третьем мире, следствием чего была постоянная смена ориентиров их внешней политики. Так, после смерти Г. А. Насера новый президент Арабской Республики Египет А. Садат взял курс на свертывание советского военного присутствия, и ВМФ лишился пунктов базирования в заливе Мерса-Матрух и в Порт-Саиде. Из-за позиции, занятой СССР во время Сомалийско-эфиопской войны 1977 года, была утрачена возможность использовать как пункт материально-технического обеспечения ВМФ порт Бербера, расположенный в стратегически важном районе Африканского Рога. Взамен пришлось срочно создавать ПМТО в Дахлаке (Эфиопия) и на острове Сокотра (Южный Йемен). Другой причиной являлось равнодушие к проблемам ВМФ руководства министерств иностранных дел, внешней торговли и Государственного комитета по внешним экономическим связям СССР.

Их совместная работа с главным командованием ВМФ в этом направлении началась лишь
в первой половине 1980-х. Благодаря этому в 1984 году было подписано межправительственное Соглашение с Южным Йеменом о создании в порту Аден ПМТО, имевшего большие возможности по обеспечению заходов советских кораблей боевой службы и их ремонту.

Свертывание системы ПМТО началось по мере снижения интенсивности несения боевой службы и ухода СССР из районов, которые ранее рассматривались как зона его жизненно важных интересов.