23 апреля 1695 года дивизии генерала Патрика Гордона выступили из Тамбова. Войско состояло из Бутырского выборного полка, 4 солдатских полков тамбовского разряда и 7 полков московских стрельцов общей численностью 9500 человек с 43 пушками и 10 мортирами. Он рассчитывал пройти расстояние в 800 километров до Черкасского городка за три недели. Но расчеты Гордона не оправдались. Его войска прибыли в Черкаск только 20 июня. Донские казаки донесли Гордону, что турки усиленно готовятся к обороне Азова. Ранее станичный атаман Григорий Белицкий докладывал в Москве что «азовский бей и янычанский ага с азовскими служилыми людьми с 3000 человек и больше» сделали вылазку под Черкаск, и атаман Фрол Минаев с 500 казаками с боем и небольшими потерями отогнали этих разведчиков «50 казаков поранено, а до смерти убит один, да 9 человек казаков в полон взяты».
30 апреля Петр Алексеевич «плавным ходом» на 1250 судах выступил из Москвы по рекам с дивизиями генерала Федора Головина численностью 7000 человек. В их составе были полки «нового устройства»: Преображенский и Семеновский, а также 5 полков московских стрельцов под командованием Сухарева, Колзакова, Озерова, Батурина Голицына. Они по легенде отправлялись как бы на Астрахань и Персию. Генеральство Франца Лефорта было самым сильным и состояло из 13 000 воинов при 104 мортирах и 44 больших пищалях, всё это было размещено на баркасах. Запас пороха был 30 000 пудов, так же 32 700 гранат, ядер и бомб. Для своего времени эта артиллерия по числу орудий и количеству боевых запасов была очень мощной. Почти два месяца продолжался поход по Волге, погода стояла холодная и дули сильные ветры. Суда, построенные под столицей, были плохого качества, кормщики управляющими ими были неопытны. «Ветры нас крепко держали… а больше всех задержка от глупых кормщиков и работников, которые именем слывут мастеры, а дело от них, что земля от неба» — так писал Государь в Москву. Наконец все суда 7 июня прибыли к Царицыну. Здесь пришлось Головину и Лефорту выгружаться на берег с трудом вытаскивать баркасы, ставить их на колеса и притаскиваться степью до Паншина городка на Дон. Многое пришлось тащить на плечах солдат, так как при войске было всего 500 конных и не было ни артиллеристских ни обозных лошадей. В период с 11 по 15 июня 1695 г., близ Раздорского городка переправлялась через Дон русская армия под командованием генерала Патрика Гордона, направлявшаяся на Азов. Сюда же пришли Доном барки с припасами для армии. Довольствие армии предполагалось осуществлять подвозом по реке. Для этого зимой 1695 г. развернулась постройка стругов в районе Воронежа под надзором стольника Кузьмы Титова. Всего было поставлено более 1000 стругов в Паншин городок. Погрузка пушек и снарядов продолжалась 5 дней. Здесь Гордона встретил Войсковой атаман Фрол Минаев, они долго беседовали между собой, и атаман советовал генералу не ходить под Азов до прибытия всей армии.