1 апреля Гордон получил из Москвы грамотку держать поход в секрете, а атамана донских казаков предупредить, чтоб не пропустил бы никаких вестей из Москвы в Азов.
Да и сами московские правители приняли донские вести к сведению и в отдельной грамоте от 6 апреля донцам прописали:
«Марта в 29 день писали к нам, великем государем, вы, атаманы и казаки, с станичным своим атаманом с Григорием Белицким с товарыщи, что по нашему указу и по грамотам ледники вы строить зачали и льдом накладете, а Пятиизбянскою станицею ледник указной осыпной построен и льдом накладен будет. Да нам же известно, вы пишете про явную измену Аюкая тайши и его улусных людей и астораханских юртовых татар, что они про нынешнее наше воинское намерение, будучи в Азове, ведомость учинили, и по тем их вестем о всем ныне в Азове ведомо. И февраля в последних числех послали азовские жители от себя Крымскою и Нагайскою стороною под наши украинные городы, к Мояцкому и к Цареву Борисову, и в иные места, и к вам и к понизовым городам для подлинной ведомости подъезды свои; а к Аюкаю послали с подарки, с пансырми и с ружьем. А ведомо вам о том учинилось подлинно от выходцев из Азова, которые сказывают, что они, азовцы, у того Аюкая просят себе вспоможения и чаят, что он хочет к ним послать едисанских татар. И вы, сведав про те их неприятельские походы, марта в первых числех послали от себя за йими, азовцами, калмыков и казаков на шляхи их, чтоб их от такого намерения отвратить и как бы над ними поиск учинить…». Вот так перечислили казакам все их писанные речи, чтоб потом не отпирались. И время указали — февраль, когда, может, самим московитам ничего известно не было. Закончили же соответственно: «И мы за то жалуем вас, атаманов и казаков и все Войско Донское, милостиво похваляем. И вы б и впредь нам (…) служили и над неприятели, бусурманы, азовцами и над иными их татарскими юртами, где доведется, воинские промыслы чинили по прежнему своему войсковому обычаю и, о поведении их, неприятелском, проведывая, писали в верх по Дону, к генералу нашему к Петру Ивановичу Гордону и во всем остерегателство ему чинили, со всяким радением и прилежанием; а он, генерал, с ратными людми идет к вам в войско, в Черкаской». Получите и встречайте…
Действительно, 7 апреля Гордон из Тамбова выступил, но шел не три недели, а больше двух месяцев.
Раздражение и враждебность казаков, видимо, бросалась в глаза. В «Истории Петра Великого» А. Г. Брикнера, профессора Дерптского университета, сказано: «Гордон, находившийся в авангарде, должен был употреблять большие усилия для того, чтобы принудить казацкого атамана Фрола Минаева к энергическим действиям. Из бесед Гордона с ним видно, что и в настоящем случае казацкий элемент оказался ненадежным, шатким, своевольным, склонным к измене».
Но атаманы донские стали умны и осторожны, напропалую не лезли. Да и Гордон умел себя с ними вести. Судя по дневникам Гордона, ему довелось обучаться в Коллегии иезуитов, а затем воевать против турок и татар, начиная с 1664 года, вместе с запорожскими и верными России украинскими казаками, и донские казаки в этих походах участвовали. Сам атаман Фрол Минаев под командованием Гордона в 1678 году с донцами Чигирин оборонял.
25 мая Гордон вышел к городку Усть-Хоперскому и 26-го переправился через Дон на судах, которые подошли из Воронежа с провиантом. Дальше он пошел степью, пересекая излучину Дона, и, согласно дневнику самого Гордона, 4 июня его передовая дивизия вышла к Донцу.
Отсюда Гордон сообщил Минаеву в Черкасск о своем подходе, просил указать переправу через Дон и сделать необходимые приготовления. К 8-му июня, отдохнув на берегу красивой реки, стрельцы построили мост через Донец. Строили долго, и Гордон записал в дневнике, что леность, безволие или неумелость стрельцов сильно тормозили работу.
9-го вечером дивизия была на правом берегу Донца, 10-го двинулась дальше со всеми воинскими предосторожностями, и в этот же день пришел ответ из Черкасска. Фрол Минаев предупреждал о большой трудности пути и прислал проводника.
11-го Гордон был у Дона возле Раздор, где уже поджидали барки с запасами. 13-го барки начали переправлять полки, а 14-го, около шести вечера, в лагерь Гордона на Сухом Донце приехали Войсковой атаман со старшиной. Казаки убеждали генерала не трогаться с места до сбора всего царского войска, но тот настаивал, что надо двигаться дальше, ссылался при этом на царский указ и потребовал, чтобы казаки присоединились к нему всей своей силой. Они изъявили готовность повиноваться указу государей, но на требование следовать вместе с Гордоном и подчиняться ему согласились неохотно.