В этот период наметилось сотрудничество Индонезии с Советским Союзом. Уже 8 августа 1959 г. в Индонезию направляются две советские подводные лодки 613 проекта (С-91 и С-79) под польским флагом. Подготовку индонезийские экипажи этих пл проходили в Польше, и по легенде передача лодок Индонезийским военно-морским силам должна была проходить как бы от Польской Республики. Командиром пл С-91 на переход в Индонезию был назначен капитан 2 ранга Воловик Федор Степанович, старшим помощником – капитан-лейтенант Лебедько Владимир Георгиевич, будущий контр-адмирал, помощником командира – капитан-лейтенант Белобородов Владимир Ильич, однокашник А. Батаршева и В. Любимова. Способный, грамотный подводник и прекрасный товарищ. Весьма лестную характеристику дает ему В. Г. Лебедько:
«Новый помощник вошел в наш коллектив, как будто он всегда был с нами. Я с удовольствием вспоминаю совместную с ним службу. Его отличительными особенностями были исполнительность и умение так отдавать приказания, не выполнить которые было просто нельзя. Правда, у него тоже что-то было со здоровьем, но он никогда на это не жаловался и с чувством высокой ответственности выполнял свои обязанности помощника командира» [10,
Врачом на этой пл служил корабельный врач-подводник капитан медицинской службы Альберт Васильевич Максимов. В последующем походе пл в Индонезию в 1962 году майору м / с А. Максимову предстоит участвовать уже в качестве флагманского врача 54-й обпл ТОФ. А в последствии он будет назначен заместителем главного врача ВМФ СССР, в запас выйдет в звании генерал-майора.
Командиром пл С-79 был назначен капитан 2 ранга Владимир Сергеевич Сусоев, старшим помощником командира – старший лейтенант Александр Сергеевич Гаврильченко, по определению В. Г. Лебедько, «несколько тщеславный, но всегда обязательный, простой и без хитрости честный человек», всех вокруг себя, в том числе и своего друга Лебедько, называвший Васьками.
25 августа 1959 г. подводные лодки вошли на внешний рейд Военно-морской базы Сурабая. Первый поход подводных лодок в Индонезию был завершен. Уже в это время, как утверждает В. Г. Лебедько, в военной гавани находились торпедные катера, малые противолодочные корабли, эскадренный миноносец проекта 30-бис, пришедшие из Советского Союза еще ранее.
Общая политическая обстановка в стране, как описывает его В. Г. Лебедько, характеризовалась следующим образом: