Для двойного наступления были сформированы две очень непохожие одна на другую русские армии. Восточная армия, которой надлежало двигаться вниз по Дону на штурм мощной турецкой крепости Азов, состояла из потешного войска Петра – солдат, атаковавших или оборонявших Прешпург на Кожуховских учениях прошлой осенью. В нее входили новые Преображенский и Семеновский гвардейские полки, стрельцы и обученная европейцами артиллерия и кавалерия – 31 000 солдат, разделенных на три отряда под командованием Лефорта, Головина и Гордона. Чтобы избежать соперничества, ни один из троих не был назначен верховным главнокомандующим. Каждому отряду следовало действовать самостоятельно, а решения, относящиеся ко всей армии, трем генералам предстояло принимать совместно в присутствии двадцатитрехлетнего бомбардира Питера.
Второе, или западное, крыло русского наступления, которому предписывалось следовать вниз по Днепру и атаковать крупные турецкие крепости в Очакове и Казикермене и три крепости поменьше, охранявшие устье реки, включало значительно более многочисленное традиционное русское войско под началом боярина Бориса Шереметева. Эта армия напоминала огромные полчища, которые водил на юг Голицын: 120 000 солдат, главным образом крестьяне-ополченцы, призванные по старинке на одно лето для участия в походе. По генеральному замыслу, войска Шереметева выступали как вспомогательные, дополняющие действия армии Петра. Их цель была не просто занять днепровские крепости, но также отвлечь главные силы татарской конницы от броска на восток, к Азову, осаждаемому отрядами Петра. Кроме того, царь надеялся, что, благодаря присутствию этого мощного прикрытия, Крым будет отрезан от европейских владений Османской империи на западе и, следовательно, татарское войско не сможет совершить свой обычный ежегодный поход на соединение с армией султана на Балканах. Этим Россия окажет весомую помощь своим попавшим в тяжелое положение союзникам. Далее, сам факт появления огромной русской армии на Украине, конечно, должен был упрочить влияние царя на вечно колеблющихся, легко поддающихся различным влияниям казаков.
Как только план кампании был составлен, Петр погрузился в приготовления. Захлебываясь от восторга, он писал Апраксину в Архангельск: «Шутили под Кожуховом, а теперь под Азов играть едем».
Отряд Гордона первым подготовился к походу и в марте выступил из Москвы на юг через степи, «густо поросшие цветами и травами – спаржей, диким тимьяном, майораном, тюльпанами, гвоздикой, медуницей и левкоями», как значится в дневнике командующего. Петр, Лефорт и Головин с главными силами двинулись в мае, погрузившись на баржи прямо на Москве-реке, и направились вниз по течению, чтобы попасть в Волгу. Их путь лежал вниз по Волге до Царицына, а там пушки и припасы перетащили волоком в низовья Дона и погрузили на другие суда. Продвигались медленно, потому что баржи то и дело давали течь, а гребцы были неопытны. Рассерженный Петр написал Виниусу: «Болше всех задершка была от глупых кормщиков и работников, каторые именем словут мастеры, а дело от них, что земля от неба».
