После ухода немцев первой военной перевозкой была отправка 29 ноября 1918 года на пароходе «Саратов» частей Добровольческой армии из Новороссийска в Керчь и Ялту. Анатолий Павлович Ваксмут, ясно понимавший сложившуюся ситуацию со странным саботажем Каниным приказов Главнокомандующего, горячо взялся за дело. Прибыв в Севастополь, в штаб Украинского флота, он пытался добиться приема у командующего украинским флотом контр-адмирала Николая Ивановича Черниловского-Сокол, но безуспешно. В течение двух недель делегация флота ВСЮР пыталась организовать переговоры, но гетманские адмиралы упорно избегали официальных встреч и уклонялись от переписки. Возрождение русского флота на Черном море даже в столь ничтожном виде, как один корабль, пугало гетманское правительство в Киеве, которому мерещилась в этом неизбежная потеря мнимой независимости. Осознав, что положительного ответа на просьбу командования ВСЮР им так и не добиться, Анатолий Ваксмут и его офицеры поспешили вернуться в Новороссийск. Дело завершилось тем, что ввиду бездействия адмирала В. А. Канина и его штаба приказом Главнокомандующего от 25 марта должность командующего несуществующего флота была упразднена. Вместо этого на должность «Главного командира судов и портов Черного моря» был назначен энергичный контр-адмирал М. П. Саблин, который 2 апреля прибыл в Севастополь. Но время было упущено, так как до эвакуации оставалось менее двух недель.

По возвращении в Новороссийский порт старший лейтенант Ваксмут обратил внимание на стоявший там «бесхозный» ледокол с ободряющим названием «Полезный». Ваксмут доложил морскому министру о том, что переговоры успеха не имели, однако, дабы не откладывать создание Белого флота в долгий ящик, по его мнению, имело смысл «реквизировать» гражданское судно, которое он заметил, и вооружить его, положив тем самым начало новой флотилии. Получив одобрение, Ваксмут был направлен в подчинение старшему лейтенанту Сергею Ивановичу Медведеву, назначенному новым командиром ледокола. Стараниями молодых офицеров на ледокол были привезены с завода и установлены 75-мм орудия, и над его кормой ввысь взмыл Андреевский флаг. Анатолий Петрович Ваксмут был назначен старшим офицером «Полезного», а артиллерийским офицером на корабль прибыл лейтенант Балтийского флотского экипажа Сергей Яковлевич Ильвов. Это был испытанный участник 1-го Кубанского похода, который он прошел вместе со своим братом Борисом, тоже лейтенантом Балтийского флотского экипажа и его женой Зинаидой Валериановной Ильвовой, служившей в Морской роте Добровольческой армии сестрой милосердия. Штурманом на «Полезном» стал мичман Михаил Иванович Тихомиров. Судьба ледокола «Полезный» сложилась таким образом, что с первых же дней он как боевое судно принял участие в боевых операциях, курсируя у северо-западных берегов Азовского моря, от Геническа до Мариуполя, и прикрывая с моря боевые операции войск ВСЮР. Позже ледокол был выслан обеспечивать охрану Арабатской стрелки и позиций белых на Ак-Манае.

На эти позиции к ледоколу несколько раз подходила подводная лодка «Тюлень» для оказания кратковременной помощи. Лодкой командовал капитан 2-го ранга Владимир Владимирович Погорецкий, бывший некогда русским морским агентом в Британии. Над лодкой, приходившей в надводном положении, развевался Андреевский флаг. Подводная лодка «Тюлень» была заложена 16 августа 1913 года, спущена на воду 19 октября 1913 года. Она успешно участвовала в Первой мировой войне на Черном море и по праву считалась одной из наиболее удачливых русских подводных лодок, что в немалой степени являлось заслугой ее командира, тогда старшего лейтенанта Михаила Александровича Китицына, отбывшего в 1918 году на крейсере «Орел» в Японию, а после принимавшего активное участие в борьбе с большевиками. Китицын ходил на кораблях Сибирской флотилии, и одно время даже заведовал гардемаринскими классами в должности начальника Морского училища во Владивостоке. Его подводная лодка по время войны захватила и потопила только в 1915 году пять парусников. В 1916 году от ее умелых действий пострадали 21 парусник и три парохода, в том числе хорошо вооруженный военный транспорт «Родосто» (6000 т). «Тюлень» привел его, несмотря на возникший на нем пожар, в качестве «приза» в Севастополь. Захват этого парохода является, пожалуй, единственным случаем в нашем флоте, когда подводная лодка после артиллерийского боя с судном противника не только вышла из него победителем, но и сумела привести его в свой порт.

История этого небольшого сражения достойна для отдельного рассказа. Заканчивался четвертый день боевого дежурства подводной лодки «Тюлень» у турецких берегов на важной морской коммуникации противника Зонгулдак — Стамбул, по которой осуществлялась основная поставка угля из Зонгулдакского угольного бассейна. Лодка находилась в надводном положении недалеко от острова Кефкен, когда в 22 часа сигнальщик заметил большой пароход, шедший от Босфора вдоль турецкого берега. По сигналу боевой тревоги орудийные расчеты двух 75-мм пушек заняли свои места, и Китицын повел лодку вокруг Кефкена, чтобы опередить пароход, внезапно его атаковать и отжать от турецкого берега в море. Для экипажа «Тюленя» это была не первая артиллерийская стрельба по турецким судам, и всегда после первых же выстрелов турецкие команды покидали обреченное судно, которое затем пускалось на дно.

Однако на сей раз так не произошло. В 22 часа 45 минут с лодки прозвучал первый выстрел, и сразу же в ответ с парохода грянули два орудия (как выяснилось потом, на «Родосто» были 88-мм и 57-мм пушки). Сгущавшаяся темнота, нервное напряжение и нехватка опыта не позволили противнику вести точный огонь. Он, не сумев разобрать силуэт русского корабля, по частоте выстрелов принял подводную лодку за эсминец. Прицелы его орудий были выставлены на 8–10 кабельтовых, в то время как фактически бой шел на дистанции 5–6 кабельтовых. Из 30 выпущенных с парохода снарядов ни один не причинил лодке повреждений. Зато огонь комендоров «Тюленя» был точным. В течение 50 минут с лодки было выпущено 46 снарядов, около 30 из которых попали в цель. Часть команды парохода со своим офицером сбежала на шлюпке. На пароходе вспыхнул пожар, но он выпустил дымовую завесу и упорно не желал сдаваться. Когда на подводной лодке осталось всего семь снарядов для носовой пушки, Китицын подвел лодку к «Родосто» и выпустил еще шесть снарядов по цели. Только после этого турецкий пароход стал парить и беззвучно остановился. Лодка подошла к пароходу и подняла из воды восемь человек из его команды. Призовая команда «Тюленя» в составе трех офицеров и около двадцати матросов перешла на «Родосто» и начала тушить пожары, поднимать пары и исправлять рулевое управление. К утру наши моряки повели сильно поврежденный и еще дымящийся «Родосто» под конвоем «Тюленя» к родным берегам. Вечером 31 сентября лодка и плененный пароход в сопровождении эсминца «Быстрый» благополучно пришли в Севастополь. За боевые успехи и героизм во время Первой мировой войны Михаил Александрович Китицын был награжден всеми русскими орденами и золотым Георгиевским оружием.

Летом 1916 года все тот же «Тюлень» выполнил поручение командования, довольно необычное для подводных лодок Великой войны. Штаб Черноморского флота решил обновить карты Варны, что было поручено лейтенанту Китицыну. Это было крайне рискованное задание, ибо, как стало известно, вдоль побережья Болгарии германскими минными заградителями были поставлены мины. Однако обновить карты требовала обстановка, так как в штабе флота имелись только устаревшие и крупномасштабные карты Варны. Обсуждая предстоящую операцию, флаг-капитан оперативной части Михаил Иванович Смирнов сказал Китицыну, что приказа войти в гавань ему адмирал не даст. Китицын тут же решил именно так и сделать. Во время похода на «Тюлене» находился начальник разведки флота капитан 2-го ранга Алексей Аркадьевич Нищенков. В своих воспоминаниях в эмиграции Китицын не скрывал терзавших его тогда опасений. На совещании офицеров «Тюленя» было решено идти к берегам нейтральной Румынии, а потом следовать до Варны предполагаемым прибрежным фарватером, которым пользовались румынские и болгарские каботажники.