Поручив вести за собою в Украину армию генералу принцу гессен-гамбургскому, Миних поехал в Павловск на Дону, сделал там распоряжение о нагрузке на суда артиллерии и припасов, необходимых для предположенной осады Азова, потом прибыл в Украину, осмотрел украинскую линию от Днепра до Донца, где нашел шестнадцать крепостей, каждая с земляным бруствером, с контр-эскарпом, со рвом, наполненным водою, а между укреплениями этими возведены были редуты разного размера. Миних объехал всю эту линию, охранявшуюся, как выше было сказано, ландмилицией из поселенных однодворцев, сделал нужные распоряжения о расстановке караулов и заметил, что в Бахмутской провинции линия остается открытою и на совершенное приведение ее в надлежащее положение необходимы работы. С этой целью Миних потребовал 53263 человека рабочих. Управлявший тогда малороссийским краем князь Шаховской, в отвеит на такое затребование, доносил правительству, что такого рода работы будут крайне разорительны для народа. Миних со своей стороны доносил, что, обозревши тогдашнее состояние Украины, он ясно видит, что разорение народа действительно заметно, но оно происходит не от работ, a от дурного управления, во главе которого стоял Шаховской: полковниками и сотниками ставятся люди неспособные, везде стараются разбогатеть за счет подчиненных, люди богатые стараются отлынивать от службы, и только бедных посылают в походы. Казаки, недовольные несправедливостями своего начальства, убегают и пристают к владельцам земель, обещающим поселенцам льготные годы, иные же бегут к татарам, и вместе с ними идут воевать против России. От этого вообще казачество в Гетманщине умалилось: прежде, бывало, можно было собрать казаков тысяч сто, а в последнее время, когда объявлен был поход Леонтьева в Крым, их едва набралось двенадцать тысяч семьсот тридцать. Тут Миних сошелся с запорожцами, которых он нашел в воинском отношении гораздо лучше, чем малороссийских городовых казаков, и с запорожскими старшинами имел совещание в Царичинке. Запорожцы дали ему совет выступить в поход в степь с ранней весны, когда еще не совершенно высохнут воды от тающих снегов, а молодая трава еще не будет сожжена. Миних нашел этот совет подходящим и в марте съездил к Азову, с которого надлежало начинать военные действия. Он поручил вести осаду Азова генералу Левашову, а сам возвратился к своему войску в Украину, снова советовался с запорожскими старшинами и десятого апреля двинулся в поход в степь. С ним было 54000 войска российского и 12000 казаков (5000 донских, 4000 украинских и 3000 запорожцев). По известию жизнеописателя Минихова, обоз, отправлявшийся с этой военной силой, простирался до девяти тысяч возов, и на каждый полк приходилось их двести пятьдесят. Одних маркитантов было до семи тысяч. Весь обоз не пошел с войском; значительная часть его с тяжелой артиллерией поручена была князю Трубецкому, который должен был доставить боевые и съестные припасы в сопровождении оставленной для того части войска, прежде расставленной в более отдаленном крае на квартирах.
Армия двинулась в степь пятью колоннами, находившимися под командою генералов Шпигеля, принца гессен-гамбургского, Измайлова, Леонтьева и Тараканова. Сам главнокомандующий Миних шел в авангарде. Запорожцы говорили, что на пути своем русское войско найдет себе корм и фураж; Миних доверился им и не очень заботился о скорейшем подвозе запасов князем Трубецким, а этот князь так медлил, что дошел тогда уже, когда Миних окончил свой поход. Для обеспечения сообщения войску с Украиной Миних на пути через степь приказывал устраивать редуты на расстоянии пяти и десяти верст один от другого и оставлять в каждом по десяти солдат и по тридцати казаков под наблюдением обер-офицера, а на трех больших ретраншементах от 400 до 500 человек со штаб-офицером.
После незначительных стычек с неприятелем колонны Шпигеля, армия 28 мая приближалась к Перекопу. Перекопский перешеек был прокопан рвом длиною на семь верст: ров шириною доходил до двенадцати, а глубиною до семи сажен. За этим рвом был вал высотою до 70 футов от вершины до дна рва. Шесть каменных башен прикрывали всю линию вала; за этим валом была крепость Перекопская. Хан, как сообщали пленники, стоял недалеко со стотысячным войском.
Миних начал с того, что написал хану, извещая его, что пришел с войском наказать татар, производивших набеги на русские владения, и просил хана добровольно впустить в Перекопскую крепость русский гарнизон и признать над собою первенство российской императрицы; иначе – он грозил опустошить весь Крым. Хан прислал мурзу с ответом в таком смысле: хан состоит данником турецкого государя и не хочет изменять ему; в Перекоп не может впускать русских, потому что там помещен турецкий гарнизон не от крымского хана, а от самой Турции; татары не подавали повода к войне, а если чинили набеги, то это делали ногаи, и русские войска могут с ними расправляться, как делалось и прежде: эти люди, хотя и состоят под властью хана, но не всегда послушны этой власти и позволяют себе своевольства. В довершение хан просил фельдмаршала приостановить военные действия и тогда уже вступить в объяснения.
Но Миних не затем пришел, чтобы проводить время в объяснениях. Отправивши мурзу ханского с отказом, фельдмаршал на другой день еще до рассвета послал две тысячи пятьсот человек вправо по направлению к перекопской линии, и в то же время русское войско двинулось всей массой влево. Татары, обманутые фальшивым движением двухтысячепятисотенного отряда, бросились на него, и вдруг нежданно увидали русские силы совсем на другой стороне. Русские дошли до рва и на короткое время остановились. Ров был очень широк. Но ров этот был сух. Солдаты спустились на дно, а оттуда стали карабкаться на вал. Вместо лестниц им служили пики, штыки и рогатки. Задние подсаживали передних и потом, держась за них, сами взбирались, и так добрались на вершину вала под сильным неприятельским огнем. Такая неустрашимость поразила татар: они бежали. В башнях сидели турецкие янычары. По приказанию Миниха принц гессен-гамбургский послал санкт-петербургского гренадерского полка капитана Манштейна с шестьюдесятью человек его роты к одной из башен. Гренадеры прорубили двери: Манштейн вошел внутрь и потребовал сдачи. Янычары, безусловно, согласились и стали класть оружие, но тут между гренадерами и янычарами возник спор, а потом и драка: янычары убили шестерых и ранили шестнадцать гренадеров; гренадеры перекололи всех янычар, а их было в башне сто шестьдесят. Тогда янычары, сидевшие в прочих башнях, покинули их и бежали вслед за татарами. Миних потребовал от перекопского коменданта сдачи: обещано было проводить всех до приморской пристани для отплытия в Турцию. Комендант на все согласился. Но когда турки положили оружие, их всех объявили военнопленными под тем предлогом, что, вопреки мирному договору, задержано было двести русских купцов, и когда им возвратят свободу, тогда и взятые в Перекопе турки будут oтпущены в отечество.
Город Перекоп, заключавший в себе до 800 деревянных домов и окруженный стеной из песчаника, рассыпавшегося от пушечных выстрелов, был тотчас занят одним русским полком, а 4 июня Миних отправил генерал-лейтенанта Леонтьева с десятью тысячами к Кинбурну. С оставшимися генералами Миних держал военный совет – что делать далее. Многие были такого мнения, что не следует забиваться в глубь страны, так как продовольствия для войска оставалось не более как на двенадцать дней, а лучше укрепиться у Перекопа и подождать прибытия кн. Трубецкого с обозом. Миних противился этому и настаивал, что надобно идти вперед и нанести страх татарам; он надеялся, что обоз поспеет и догонит их, а если бы и запоздал, то войско может продовольствоваться за счет неприятельского края.
И пошло войско по безводной пустыне в глубину Крымского полуострова. Татары умышленно портили воду, и без того скудную в колодцах. Их летучие отряды беспокоили войско, двигавшееся четвероугольником. Когда расположилось войско на дневку в Бальчике, к нему приблизились татары. Откомандированный против них генерал-майор Гейн хотя не потерпел поражения, но не исполнил в точности поручения, данного фельдмаршалом, и за это немедленно был предан военному суду и разжалован в солдаты. Миних чрезвычайно строго относился к делу дисциплины в войске. Пошли дни за днями. Жара была нестерпимая. Солдаты пропадали от жажды и зноя. Подвоз ожидаемых запасов не приходил по медленности князя Трубецкого. Генерал принц гессен-гамбургский, уже прежде враждовавший с Минихом, а за ним и другие генералы, в числе их и близкий родственник Бирона, носивший ту же фамилию, распускали о Минихе между подчиненными упреки, что он для удовлетворения своего честолюбия губит целое войско и поступает совсем против желания и предписаний петербургского двора. К счастью Миниха, войско, все еще не дождавшись князя Трубецкого с обозом, вдруг нашло себе продовольствие. На десятый день пути от Перекопа достигло оно города Хазлейва (Козлов-Евпатория) и вошло туда без всякого сопротивления: все мусульманские обитатели этого города заранее убежали оттуда, успевши взять с собою, что возможно было на скорую руку, и зажгли за собою дома христианских купцов. Но бежавшие всего с собою забрать не были в состоянии. Русские в опустелом и полуобгорелом городе отыскали закопанные в земле драгоценности – золото, серебро, жемчуг; меди, железа и свинцу была громада, рису и пшеницы было такое изобилие, что Миних раздал их в качестве провианта солдатам на двадцать четыре дня.