Двадцатого января 1695 года на Постельном крыльце Кремлевского дворца был объявлен приказ служилым людям собираться в поход в Белгород и Севск к боярину Борису Петровичу Шереметеву для похода на Крым. Цель похода сознательно держалась в тайне – в действительности поход готовился не на Крым, а к Азову. На военном совете, состоявшемся 21 февраля, было решено отправить под Азов сухим путем десятитысячный отряд под командованием генерала Гордона с целью воспрепятствовать приходу в город турецких подкреплений. Главные силы с артиллерией и амуницией должны были следовать водой по рекам Москве, Оке и Волге до Царицына, а оттуда пешим ходом двинуться к Паншину, расположенному на Дону в том месте, где излучина реки ближе всего подходит к Волге. Гордон отправился в путь 6 марта, а основные полки, посаженные на струги, отчалили от Каменного моста
О ходе подготовки к первому Азовскому походу Лефорт поведал в письме к брату, отправленном 16 февраля 1695 года:
«Сейчас я могу вам сказать следующее: вся страна готовится и собирает полки, чтобы, когда вскроются реки, отправиться с его царским величеством Петром Алексеевичем. У нас четыре армии. Первая отправится водным путем до турецкого города Азова, который его величество будет осаждать. Отсюда отправляется самая красивая артиллерия, какую только можно видеть. Четыре генерала должны следовать за его величеством, и они уже получили распоряжения. Первого вы знаете, это я, ваш слуга. Мой полк, в сущности, по численности шестой, насчитывает больше двенадцати тысяч человек. И кроме того у меня есть все, что нужно, т. е. 24 больших пушки и 24 больших мортиры, чтобы совсем разрушить город. Второй генерал – мой шурин Гордон, с восемью тысячами человек других войск, так как его полк насчитывает только четыре тысячи. Еще один русский генерал с тем же числом людей и с таким же количеством пушек и мортир. Еще один – генерал от артиллерии. Он будет командовать казачьими войсками со стороны Дона и несколькими полками со стороны Астрахани и Казани. Вторая армия – гетманская, т. е. казацкого князя, у него более 60 тысяч человек, он двинется со стороны Перекопа или Казы-Керменя и нападет на несколько городов. Белгородская армия является третьей, она насчитывает более 40 тысяч верховых и солдат. Она не разъединится с гетманской. Четвертая будет стоять на границе со стороны Севска в резерве, командовали не зависимые друг от друга командующие, что противоречило принципам воинской субординации. Первое соединение численностью около десяти тысяч под командованием генерала Гордона должно было достичь Азова по суше. Задача, поставленная Гордону, состояла в том, чтобы, расположившись у стен крепости, воспрепятствовать подходу к ней турецких подкреплений. 24 июля полки Гордона встали лагерем под Азовом, но военных действий не открывали, ожидая прибытия главных войск.
Большинство бояр следуют за его величеством – их три тысячи. Начинают постепенно покидать лагеря. Пятеро из моих полковников отправляются на этой неделе, чтобы присоединиться к своим полкам». Таково было расположение войск по плану на середину февраля. Реальная дислокация войск месяц спустя после отправки письма отличается от описанной Лефортом. Войска были разбиты на три соединения, каждым из которых
Второе соединение под командой Автомона Михайловича Головина, численностью около семи тысяч человек, и третье под командованием Лефорта, численностью в тринадцать тысяч человек, погрузились на Москве-реке в струги и отправились в путь при пушечной пальбе 28 апреля. Четвертой армией, на долю которой выпали операции против Крыма, командовал Б. П. Шереметев. Эта армия действовала вдали от основных корпусов. Ее главная задача состояла в том, чтобы ввести в заблуждение турок, которые должны были полагать, что новый поход, как и походы Голицына, будет направлен в Крым.