Каспийская военная флотилия в составе ВСЮР была создана в феврале — марте 1919 г. после отступления частей советской 9-й армии с западного побережья Каспия. В это время на Каспийском море господствовали англичане. Британский отряд, состоявший из быстроходных катеров и переоборудованных в боевые корабли коммерческих судов, возглавлял коммодор Норрис. Первоначально речь шла не о создании русской морской части, а о службе русских моряков в составе английской флотилии. По словам Кадесникова, «с предлагаемой службой в составе английской флотилии русских моряков примиряли два важных обстоятельства: на английских кораблях будут подняты Андреевские флаги и, состоя в числе личного состава флотилии, они всегда будут в курсе эгоистично „мудрой“ политики лукавого Альбиона, что во всяком случае необходимо для белого Верховного командования и бесценно для будущей объективно правдивой истории».
Первоначально корабли предполагалось укомплектовать уральскими казаками и киргизами, но тяжелое положение в Уральском войске и невозможность занятия казаками должностей, требующих высокой квалификации, не позволили осуществить этот план. Белому командованию пришлось отправить офицеров и матросов из Севастополя. Эшелон возглавил капитан 2-го ранга Б.М. Пышнов, ставший первым командиром флотилии. Эшелон прибыл в Петровск (совр. Махачкала) 21 марта, где личный состав был придан отряду генерала Пржевальского и первоначально нес наряды гарнизонной службы в городе. Порт находился под контролем англичан, и создание конкурирующей морской силы на Каспии не вызывало восторга у британского командования. Но все же союзнический статус обязывал англичан помогать белым и содействовать созданию антибольшевистской военной флотилии. 7 марта 1919 г. командующим формируемой флотилии назначили капитана 1-го ранга А.И. Сергеева. Из-за противодействия азербайджанского правительства и англичан создать базу флотилии в Баку не удалось, и ей пришлось базироваться в районе Петровска. В июне появился приказ об откомандировании на флотилию всех морских офицеров с фронта (в частности, капитан 2-го ранга А.П. Ваксмут прибыл из Царицына с десятью офицерами). Рядовой состав укомплектовали астраханскими рыбаками-добровольцами.
В связи с тем, что большинство кораблей бывшей Каспийской флотилии Императорского флота находилось в Баку в распоряжении правительства Азербайджанской республики, а крупнотоннажные коммерческие суда в основном захватили англичане, организационная группа первоначально могла использовать только небольшие пароходы и парусно-моторные шхуны. Постепенно англичане начали передавать русским антибольшевистским силам русские же корабли.