В Новороссийске группа офицеров-энтузиастов под руководством старшего лейтенанта Анатолия Петровича Ваксмута, бывшего командира парохода «Кубанец» Донской флотилии, получила предписание от вице-адмирала Александра Михайловича Герасимова. Предписание гласило: команде доверенных офицеров отправиться в Севастополь и под любым предлогом получить в распоряжение ВСЮР полноценный боевой корабль. Причины для этого шага были весьма существенные. Безуспешная попытка получить военное судно при посредстве самого Деникина, направлявшего некогда письмо адмиралу Василию Александровичу Канину, лишь придала задора упорному в достижении цели Ваксмуту. В Симферополе образовалось марионеточное крымское правительство, не признававшее генерала А. И. Деникина и претендовавшее на принадлежность ему всего, что находилось в Севастополе. Вице-адмирал Канин, которого Главнокомандующий генерал А. И. Деникин недавно назначил командующим Белым флотом, держался совершенно независимо от Екатеринодара и даже сформировал весьма многочисленный штаб. Под предлогом, что крымское правительство противится переводу кораблей в Новороссийск, а также забастовки рабочих на судоремонтном заводе, он не принимал никаких мер для восстановления кораблей. Союзники захватили все транспорты из бывших австрийских и немецких пароходов, но остальные, так же, как пароходы контролируемых правительством обществ, были в распоряжении Добровольческой армии. Однако частные судовладельцы, чтобы избежать всяких реквизиций и большевистской национализации, стремились вывести свои пароходы за проливы. Во избежание этого было опубликовано запрещение для пароходов покидать Черное море без разрешения. Французы иногда более или менее принудительно фрахтовали пароходы для своих нужд; некоторые большие пассажирские пароходы РОПиТ до конца Гражданской войны находились в их распоряжении и, в частности, были ими использованы для репатриации русских солдат и военнопленных из Франции. Но фрахтование пароходов и военных транспортов приносило Добровольческой армии валюту, которой она расплачивалась за покупки за границей самого необходимого.
После ухода немцев первой военной перевозкой была отправка 29 ноября 1918 года на пароходе «Саратов» частей Добровольческой армии из Новороссийска в Керчь и Ялту. Анатолий Павлович Ваксмут, ясно понимавший сложившуюся ситуацию со странным саботажем Каниным приказов Главнокомандующего, горячо взялся за дело. Прибыв в Севастополь, в штаб Украинского флота, он пытался добиться приема у командующего украинским флотом контр-адмирала Николая Ивановича Черниловского-Сокол, но безуспешно. В течение двух недель делегация флота ВСЮР пыталась организовать переговоры, но гетманские адмиралы упорно избегали официальных встреч и уклонялись от переписки. Возрождение русского флота на Черном море даже в столь ничтожном виде, как один корабль, пугало гетманское правительство в Киеве, которому мерещилась в этом неизбежная потеря мнимой независимости. Осознав, что положительного ответа на просьбу командования ВСЮР им так и не добиться, Анатолий Ваксмут и его офицеры поспешили вернуться в Новороссийск. Дело завершилось тем, что ввиду бездействия адмирала В. А. Канина и его штаба приказом Главнокомандующего от 25 марта должность командующего несуществующего флота была упразднена. Вместо этого на должность «Главного командира судов и портов Черного моря» был назначен энергичный контр-адмирал М. П. Саблин, который 2 апреля прибыл в Севастополь. Но время было упущено, так как до эвакуации оставалось менее двух недель.
По возвращении в Новороссийский порт старший лейтенант Ваксмут обратил внимание на стоявший там «бесхозный» ледокол с ободряющим названием «Полезный». Ваксмут доложил морскому министру о том, что переговоры успеха не имели, однако, дабы не откладывать создание Белого флота в долгий ящик, по его мнению, имело смысл «реквизировать» гражданское судно, которое он заметил, и вооружить его, положив тем самым начало новой флотилии. Получив одобрение, Ваксмут был направлен в подчинение старшему лейтенанту Сергею Ивановичу Медведеву, назначенному новым командиром ледокола. Стараниями молодых офицеров на ледокол были привезены с завода и установлены 75-мм орудия, и над его кормой ввысь взмыл Андреевский флаг. Анатолий Петрович Ваксмут был назначен старшим офицером «Полезного», а артиллерийским офицером на корабль прибыл лейтенант Балтийского флотского экипажа Сергей Яковлевич Ильвов. Это был испытанный участник 1-го Кубанского похода, который он прошел вместе со своим братом Борисом, тоже лейтенантом Балтийского флотского экипажа и его женой Зинаидой Валериановной Ильвовой, служившей в Морской роте Добровольческой армии сестрой милосердия. Штурманом на «Полезном» стал мичман Михаил Иванович Тихомиров. Судьба ледокола «Полезный» сложилась таким образом, что с первых же дней он как боевое судно принял участие в боевых операциях, курсируя у северо-западных берегов Азовского моря, от Геническа до Мариуполя, и прикрывая с моря боевые операции войск ВСЮР. Позже ледокол был выслан обеспечивать охрану Арабатской стрелки и позиций белых на Ак-Манае.
На эти позиции к ледоколу несколько раз подходила подводная лодка «Тюлень» для оказания кратковременной помощи. Лодкой командовал капитан 2-го ранга Владимир Владимирович Погорецкий, бывший некогда русским морским агентом в Британии. Над лодкой, приходившей в надводном положении, развевался Андреевский флаг. Подводная лодка «Тюлень» была заложена 16 августа 1913 года, спущена на воду 19 октября 1913 года. Она успешно участвовала в Первой мировой войне на Черном море и по праву считалась одной из наиболее удачливых русских подводных лодок, что в немалой степени являлось заслугой ее командира, тогда старшего лейтенанта Михаила Александровича Китицына, отбывшего в 1918 году на крейсере «Орел» в Японию, а после принимавшего активное участие в борьбе с большевиками. Китицын ходил на кораблях Сибирской флотилии, и одно время даже заведовал гардемаринскими классами в должности начальника Морского училища во Владивостоке. Его подводная лодка по время войны захватила и потопила только в 1915 году пять парусников. В 1916 году от ее умелых действий пострадали 21 парусник и три парохода, в том числе хорошо вооруженный военный транспорт «Родосто» (6000 т). «Тюлень» привел его, несмотря на возникший на нем пожар, в качестве «приза» в Севастополь. Захват этого парохода является, пожалуй, единственным случаем в нашем флоте, когда подводная лодка после артиллерийского боя с судном противника не только вышла из него победителем, но и сумела привести его в свой порт.
История этого небольшого сражения достойна для отдельного рассказа. Заканчивался четвертый день боевого дежурства подводной лодки «Тюлень» у турецких берегов на важной морской коммуникации противника Зонгулдак — Стамбул, по которой осуществлялась основная поставка угля из Зонгулдакского угольного бассейна. Лодка находилась в надводном положении недалеко от острова Кефкен, когда в 22 часа сигнальщик заметил большой пароход, шедший от Босфора вдоль турецкого берега. По сигналу боевой тревоги орудийные расчеты двух 75-мм пушек заняли свои места, и Китицын повел лодку вокруг Кефкена, чтобы опередить пароход, внезапно его атаковать и отжать от турецкого берега в море. Для экипажа «Тюленя» это была не первая артиллерийская стрельба по турецким судам, и всегда после первых же выстрелов турецкие команды покидали обреченное судно, которое затем пускалось на дно.
