В декабре 1956 г. из состава вспомогательных сил Черноморского флота в Албанию был переведен отряд судов: танкер «Линда», землеснаряд «Землесос-7» производительностью 1200 кубов, морской буксир (500 л. с), наливная баржа и водолазный бот. Старшим на переходе был назначен капитан 1-го ранга П.А. Керенский. Процесс передачи занял месяц, албанцев пришлось сначала обучать работе с механизмами, кроме того, на судах остались наши специалисты во главе с капитанами еще на год по двустороннему договору.
По соглашению с Албанией летом 1958 г. четыре подводные лодки проекта 613 и плавбаза подводных лодок «Немчинов» перешли с Балтийского флота в албанский залив Влёра, где в удобной бухте Паши-Лиман был оборудован пункт базирования со всей необходимой для подводных сил береговой инфраструктурой. Через полгода во Влёре разместились 12 подводных лодок и две плавбазы — «Немчинов» и «Виктор Котельников». Директивой начальника штаба Черноморского флота от 27 октября 1958 г. эти лодки были объединены в 40-ю отдельную бригаду, оперативно подчиненную командующему Черноморским флотом.
Перебазирование наших подводных лодок в Средиземное море производилось по возможности скрытно. Но в декабре 1959 г. разразился грандиозный скандал. Президент США Д. Эйзенхауэр решил прокатиться по Средиземному морю на тяжелом крейсере «Де Мойн». Крейсер шел в Тунисском заливе внутри авианосного ордера. И вдруг почти у самого борта «Де Мойна» поднялся перископ. Командование соединения охватила паника. Американские эсминцы кинулись преследовать лодку.
Валентину Козлову, командиру подводной лодки С-360 (проекта 613) удалось оторваться от янки лишь на третьи сутки и в положенное время вернуться на базу во Влёру.
Нарушение подводной лодкой С-360 скрытности стало предметом разбирательства у Главкома ВМФ. Командиру светило снятие с должности. Хотя он, собственно, и не был виноват. Время для сеансов связи с подводными лодками устанавливало начальство, и, замечу, часто выбирало его безграмотно. Вот Козлов и вышел на связь в положенное время в Тунисском заливе. Спас капитана сам Хрущев. Он по «иным» каналам узнал об испуге американского командования и самого Эйзенхауэра и велел не только не наказывать, но и наградить подводников.
Помимо подводников во Влёре базировались и другие соединения флота. На острове у входа в бухту Паша-Лиман обустраивалась бригада ОВР, имевшая в своем составе дивизион тральщиков. В 1958 г. во Влёре была развернута радиодальномерная гидрографическая партия «Координатор» и другие гидрофизические партии 8-го отдельного Краснознаменного маневренного дивизиона гидрографического обеспечения Черноморского флота.
Поскольку для обеспечения нашей базы во Влёре кораблей снабжения Черноморского флота не хватало, пришлось фрахтовать суда Одесского морского пароходства для доставки в бухту Влёра необходимых грузов.
25 мая 1959 г. в Тирану на самолете Ту-104 прибыл с официальным визитом генеральный секретарь ЦК КПСС Н.С. Хрущев. Его сопровождали министр обороны СССР Р.Я. Малиновский и заместитель министра иностранных дел Н.П. Фирюбин.
Целью визита было разъяснение положений доклада о «разоблачении культа личности», сделанного Хрущевым на XX съезде КПСС, а также согласование планов усиления советского военного присутствия на Адриатическом море.
Никита Сергеевич мечтал в противовес американским ракетам «Юпитер», развертываемым в Италии, установить наши ракеты: «…если в Албании поставить ракеты средней дальности или даже ракеты ближнего боя, то они могут накрыть всю Италию».
30 мая после нескольких дней переговоров советская делегация во главе с Хрущевым посетила советских моряков во Влёре. Их сопровождали албанские руководители Энвер Ходжа и Мехмет Шеху. Встреча началась с ритуала приветствия и обхода строя моряков, выстроившихся на плавпричале, где стояли подводные лодки. В тени у борта плавбазы «Владимир Немчинов» Никита Сергеевич пообщался несколько минут с командирами лодок, а затем отобедал на той же плавбазе и к вечеру вышел на ней на морскую прогулку к порту Саранде. Однако Ходжа был не в восторге от охаивания Сталина, и еще более его возмущал отказ Хрущева дать большие кредиты Албании.
Ходжа начал сближение с Пекином, и уже в октябре 1959 г. албанская печать заняла прокитайскую позицию по поводу огульной критики Сталина и других разногласий в коммунистическом движении.
В 1960 г. бригада продолжала пополняться кораблями: в январе с Черноморского флота прибыл корабль радиотехнической разведки «Угорь», осенью того же года в Албанию пришел второй корабль — разведчик «Краб». На Черноморском флоте был сформирован морской радиоотряд, который до декабря 1960 г. базировался на албанском острове Сазан. В базе разместилась также бригада кораблей охраны водного района, имевшая в своем составе дивизион тральщиков. В том же 1960 году во Влёре началось строительство мощной динноволновой радиостанции для связи с подводными лодками.
В 1960 г. крейсер «Куйбышев» в мае—июне и в августе посетил Албанию.
В том же 1960 году в Средиземном море было проведено учение, в котором принимали участие шесть подводных лодок отдельной бригады подводных лодок. Центральным эпизодом его стали поиск и атака ими отряда кораблей в центральной части Средиземного моря. «Флагманский корабль противника» обозначал крейсер «Куйбышев», шедший в охранении двух эсминцев со скоростью 18 узлов. При подходе к последней завесе лодок к ним пристроился американский крейсер «Олбани» с фрегатом.
Две учебные торпеды прошли впереди форштевня «Куйбышева». А начальство видело пузыри воздуха под днищем корабля — след отставал от торпеды. Далее учебные торпеды направились к американским кораблям. На «Олбани» не стали рисковать и решили «для прогулок подальше выбрать закоулок».
Зато через несколько дней янки представился шанс утереть нос русским. На советском эсминце кончался мазут, и он запросил командование пополнить запас мазута. Дозаправка осуществлялась при штилевой погоде, кильватерным способом, на скорости хода 4—5 узлов и продолжалась около 5 часов.
На следующий день корабли 6-го флота продемонстрировали, как это делается у них. Быстроходный танкер-заправщик произвел заправку американского эскадренного миноносца на скорости 18 узлов траверзным способом с дистанции 25—35 м. Полная заправка эсминца была проведена менее чем за 1,5 часа.
Несмотря на идеологические разногласия между лидерами СССР и Албании, отношения между моряками в 1960 г. продолжали оставаться хорошими. Как вспоминал контр-адмирал А.В. Загребин, весь 1960 год наши военные, в частности моряки, работали с албанцами очень дружно, никаких конфликтов не было. Был расширен порт в Дурресе, сооружались военные объекты во Влёрском заливе для базирования кораблей и противодесантной обороны побережья.
В конце 1960 г. 40-я отдельная бригада подводных лодок (ОБПЛ) передала албанскому флоту четыре подводные лодки С-241, С-242, С-358, С-360 и плавбазу «Владимир Немчинов». На церемонии передачи во Влёрском заливе, проходившей довольно торжественно, присутствовали руководители албанского флота и офицеры Генштаба вооруженных сил Албании.