Корабли и суда для данного формирования были построены в период 1737—1738 годов для содействия сухопутной армии генерал-фельдмаршала графа Б. К. Миниха против турок (османов) в кампании 1737—1739 годов[1]. При содействии вице-канцлера графа Остермана 4 января 1737 года вышел Указ Сената о постройке в Брянском адмиралтействе на реке Десна малых судов флотилии, предназначенной для действий на Днепре и в Русском (Чёрном) море.
Начало казённому судостроению в Брянске положил указ Петра I, от 1696 года, для участия в Азовском походе русских войск[2]. К весне того же года было изготовлено на верфях 42 струга больших размеров (по 21,34 метра), 46 стругов малых (13,87 — 10,67 м) и 45 лодок однодеревных. На них по Десне сплавляли к Киеву хлебные запасы, полковые и верховые пушки[3] из запасных магазинов расположенных на берегах Днепра и Дона[4].
Малые военные суда строились в Брянске (на реке Десна) и в 1724 — 1727 годах, а также происходила заготовка, на местной верфи, леса и иного материала для строительства и оснащения кораблей флотилии Армейского флота из 5 прамов и 7 галер[4], но кончина государя императора прекратила уже начатое казённое судостроение в Брянске.
В 1736 году, с началом очередной войны с Османской империей (Турцией), появилась необходимость в морской силе для противодействия турецкому флоту в Русском (Чёрном) море. Решено было возобновить судостроение в Брянске, но дело шло медленно. Только в январе 1737 года были выбраны окончательно типы судов для флотилии. Начальником флотилии назначен контр-адмирал В. А. Дмитриев-Мамонов. Решено было построить 355 судов разных типов и размеров, погрузить на них осадную артиллерию и боевые припасы и к лету 1737 года поспеть к Очакову для оказания помощи при его осаде. Но, несмотря на страшную спешку, флотилия опоздала к осаде. Первый эшелон (1-е отделение флотилии под начальством полковника Хрипунова) в составе 14 дубель-шлюпок и 70 разных судов отправлен в апреле, последний (3-е отделение (4 дуб.-шлюпки, один канчебас и 4 байдака)) выступил 1 июня, на пути к крепости Очаков экипажам (командам) судов формирования приходилось претерпевать невероятные трудности. Спущенные в Брянске суда вооружались на Десне, переходили в Днепр и следовали безостановочно до Кайдакского порога. Перед порогом их на значительном расстоянии волокли по берегу и только после третьего днепровского порога спускали на воду. В Ненасытца все суда приходилось вновь разгружать и по особому помосту волочить саженей 30, после чего их уже окончательно спускали на воду, нагружали и вели до устья Днепра. От такого плавания подводные части многих судов приходили в полную негодность. Личный состав был несоразмерно мал: на всю флотилию 6 морских офицеров и 60 матросов, остальной состав был добавлен из инвалидных и гарнизонных полков.