Первый Крымский поход показал недостаточность военных усилий, которые могли бы принудить хана не только принять хотя бы минимальные условия русской стороны, но даже начать переговоры. Подобный итог, несомненно, должен был поставить перед московским правительством и главным инициатором военной экспедиции на Крым В. В. Голицыным вопрос о необходимости расширения мер военного давления на противника, и в первую очередь об укреплении позиций России в низовьях Днепра. В Москве прекрасно понимали необходимость этого, о чем свидетельствует основание Каменного Затона и размещение там гарнизона летом 1686 г. План постройки крепостей на р. Самаре обсуждался еще на военном совете 14 июня 1687 г., а в царской жалованной грамоте новому гетману Мазепе говорилось о необходимости сооружения целой системы крепостей на р. Самаре и Орель (у ее притоков Орчика и Берестовой) «для утеснения и удержания Крыма», которые предполагалось населить «охочими малороссийскими людьми»[496].

23 мая 1688 г. полк Л. Р. Неплюева выступил в Самарский поход из Рыльска, прибыв к середине июня в Ахтырку. После сбора всех ратных людей он насчитывал около 15 тыс. человек, включая 4 рейтарских (более 3 тыс. человек), 10 солдатских полков (почти 11 тыс. человек), 1,5 тыс. слободских казаков Харьковского и 500 — Ахтырского слодобских полков[497].

Мазепа собрал для похода на Самару 20 с лишним тыс. выборных казаков Черниговского, Нежинского, Лубенского, Гадячского, Стародубского, Прилуцкого и Миргородского полков, а также конные и пешие наемные полки[498]. Помимо казаков, в гетманском войске были и два стрелецких полка — стольников и полковников Б. Ф. Дементеева и А. А. Чубарова[499]. Мазепа рассчитывал выступить из Батурина 25 мая, однако задержался, оправдываясь поздним прибытием в гетманскую ставку вышеупомянутых стрелецких полков. 13 июня стрельцы наконец прибыли в Батурин и уже на следующий день гетман выступил в поход, а 20 июня съехался в лагере под Константиновом («в урочище близ реки Сулы ниже городов Недрыгайлова и Костянтинова») с Неплюевым (прибыл без войска). Здесь Мазепа и глава Севского разряда обсудили планы дальнейших действий[500]. Статьи, посланные Мазепой в Москву по итогам этого совещания, сохранились не полностью, тем не менее они позволяют вполне определенно очертить высказанные гетманом предложения по организации Самарского похода и волновавшие его в связи с этим проблемы.

Мазепа по-прежнему отказывался мобилизовать на строительство людей из малороссийских полков, у которых наступает период «сенокосу и хлебной жатвы», соответственно, строительство должно было реализовываться силами малороссийских казаков и русских полков, каждому из которых планировалось выделить свой участок работы. В связи с недовольством запорожцев, которые могли «помириться с ордой» и тем самым спровоцировать татарский набег в район устья Самары, Мазепа по согласию с Неплюевым предлагал послать в район крепости «прибавочное войско», «с которым бы возможно было неприятелским бусурманским наступлениям давати отпор и устрашити и уняти такие неприятных голов запорожских намерения». Также гетман напоминал о необходимости выслать «в средину Малой Росии» часть Севского полка во главе с С. П. Неплюевым, который должен был расположиться «обозом под Быковым между Прилукою и Переяславом». Мазепа вновь повторял свой тезис о нецелесообразности войскам Косагова идти сразу на Запорожье (тем более что его полк еще не был готов к походу), как это планировалось изначально. Он предлагал, чтобы Косагов спустился с основным войском к устью Самары, а там уже решение о его марше на Запорожье должно было быть принято «смотря по ведомостям». Основное войско Мазепа предлагал не держать долго на Самаре и отвести его немедленно после постройки города (на нее отводилось три-четыре недели) в связи с необходимостью подготовки к будущему большому походу на Крым, оставив в качестве гарнизона 3 тыс. «ратных людей» (часть его могла быть сформирована за счет украинских казаков) с «знатным» и в «воинских делех искус ным» командиром. Наконец, после завершения строительства гетман выражал готовность даже осуществить поход вместе с русскими войсками на Перекоп, при наличии трех условий: 1) получения «подлинных доводов», что Селим-Гирей сам пойдет в поход «в полуденные страны против войск християнских цесарского величества» или вышлет туда «многие орды», в результате чего Крым «останетца в малолюдстве»; 2) если «травы в полях горети не станут и в кормах конских скудости не будет»; 3) если «от запорожцов и от городовых каковых малодушных противности какой и препятия не будет». Также Мазепа сообщал, что «чолны или лотки», которые он обещал сделать в городах своего регимента «и ратным государским людем для плавного походу отдати», уже готовы, и гетман велел их отвести по Днепру к Кодацкому острову.

Из царского ответа на статьи Мазепы сохранились лишь отдельные листы, из которых, опуская формальности, можно получить информацию лишь об одном решении, которое было принято в русской столице в ответ на гетманскую просьбу. Речь шла об указе Б. П. Шереметеву идти с полками Белгородского разряда на р. Коломак и до возвращения Мазепы и Неплюева из Самарского похода «стоять в том месте со всякою осторожностью и осмотрением, чтоб неприятелские бусурманские войска в державу их царского величества безвестно не напали»[501].

3 июля Мазепа пришел на р. Коломак, где, по всей видимости, на следующий день соединился с войсками Неплюева и Косагова. 5 июля объединенное войско двинулось к Самаре[502]. Как сообщал присутствовавший в русском войске польский резидент и брацлавский стольник С. Глосковский, великороссийские и малороссийские войска шли в следующем порядке: справа — Неплюев, в центре — Мазепа, слева — Косагов. Польский дипломат хвалил московское и казацкое войско («барзо доброе»), две трети которого составляла пехота, а треть — конница. Русско-украинские войска прибыли на назначенное для строительства место 22 июля (12 июля по старому стилю), и уже на следующий день начались работы по возведению крепости. Неплюев, Косагов, Мазепа и откомандированный для руководства стройкой инженер-иноземец полковник Вилим Фанзален разметили расположение будущих укреплений, а солдаты и казаки начали копать рвы и насыпать валы[503]. 25 июля Мазепа сообщал царям, что «рвы и валы по большой части зделаны, так и дерном належащее и потребное строение знатно оказуется, и даст Господь Бог, что всемогущею его помощию в первых числех августа так крепость станет в своем совершенстве»[504]. Гетман особенно хвалил Неплюева, который якобы пропадал на стройке с утра до вечера, несмотря на слабое здоровье, вызванное приступами с обилием мокроты[505].

В результате строительных работ к 1 августа 1688 г. были возведены земляные укрепления, а к 27 августа сооружены 260 просторных изб для гарнизона, в том числе 1 приказная и 3 воеводские избы, храм во имя Пресвятой Богородицы, 2 пороховых погреба, ледник, 17 плетневых сараев и другие строения. Центр новопостроенного города имел периметр 410 сажен и был предположительно опоясан деревянным палисадом (в описи он не упоминается), рвом и валом, на котором были оборудованы 17 пушечных раскатов. Вокруг него был устроен посад, защищенный рвом (ширина — 2,5 сажени; со стороны реки — 1,5 сажени; глубина — 1,5 сажени) с 17 выводами и валом, периметр которого составлял 1641 сажень. Переброшенные через рвы мосты были укреплены надолбами. Ратные люди Л.Р. Неплюева построили 170 двойных изб в 4 окна, 3 сарая, оборудовали 14 раскатов под орудия; полк Г. И. Косагова соорудил 50 двойных изб, 4 плетневых сарая с камышовой крышей для хранения хлеба, 3 орудийных раската; казаки Мазепы — 7 дворов, включая 6 изб с сенями и 2 светлицы, 9 плетневых сараев; два полка находившихся при гетмане стрельцов — 1 плетневый сарай с камышовой крышей. Для нужд будущего гарнизона было накошено 4047 возов сена[506].