Для сборки и достройки судов будущего „каравана" Петр избрал правый, пологий берег реки Воронеж на протяжении от города Воронежа до слободы Чижово, а также удобные места у Ступинской пристани, что находилась несколько выше Воронежа. Выбор пал на этот район потому, что отсюда имелось прямое водное сообщение с рекой Дон, а по нему – с Азовским морем. Кроме того Петр учел, что по берегам притоков реки Воронеж было много обширных лесных угодий, пригодных для заготовки необходимых лесоматериалов.
Поскольку для похода к Азову помимо военных судов требовались огромные транспортно-перевозочные средства, способные перебросить к турецкой крепости русские войска, их технику и припасы, Петр приказал построить в Козлове, Брянске и в некоторых пунктах по течению реки Воронеж 1300 стругов, 300 морских лодок и 100 плотов.
По указу Петра в Воронеж и окрестные места согнали плотников и других работных людей со всех окружающих сел и деревень, а также из Москвы, Вологды, Нижнего Новгорода, Архангельска и Астрахани. Среди них было немало талантливых русских умельцев, таких как вологодский судовой плотник Осип Щека, строивший галеры, нижегородский плотник Яков Иванов – виртуоз по части стругов.
По призыву Петра из Архангельска с иностранных судов, зимовавших в русском порту, привезли на подводах судовых плотников и других специалистов, знакомых с судостроением. Им была обещана щедрая плата за срочную работу и гарантирована быстрая доставка обратно по ее окончании. Многие десятки корабельных мастеров, подмастерьев и плотников были выписаны из Голландии, Англии и Венеции. Все это обходилось очень дорого, но подобные расходы оправдывались срочностью и важностью задуманного дела.
Всего в районе Воронежа в 1696 г. собрали более 26 тысяч плотников, возчиков и иных работников, которые были заняты на постройке судов, заготовке и подвозке для них „членов" набора корпусов и стройматериалов. Перевозки обеспечивали несколько тысяч лошадей. Сам Петр лично участвовал во всех строительных работах как рядовой корабельный плотник и кузнец, не отставая от своих соратников из числа бомбардиров-преображенцев.
К маю 1696 г. постройка и спуск на воду большей части судов были завершены. Недостроенные тоже спустили на воду, решив достраивать „на ходу" – во время перехода к Азову. Так, недостроенный 36-пушечный корабль „Апостол Павел" по приказанию Петра вышел в поход вслед за морским „караваном" в сопровождении пяти стругов, на которых везли доски и иные материалы для достройки корабля в пути.
