Полкам раздали запас хлеба на два месяца, и офицерам приказано было взять с собой, по крайней мере, столько же. Фельдмаршал хотел бы снабдить войско и большим запасом провизии, так как ее было достаточно припасено за зиму но не хватало подвод. Все-таки он не решался откладывать поход, а поручил генерал-майору князю Трубецкому позаботиться о доставке провизии в армию. Но, увы, князь Трубецкой действовал очень медленно, вполне возможно, что со злым умыслом. Отправленные им обозы не составляли и одной десятой от запланированного.
В армии Миниха были как запорожские, так и украинские (гетманские) казаки. О них Миних писал императрице: «В прежние времена гетманские казаки могли выставлять в поле до 100 000 человек; в 1733 г. число служащих убавлено до 30 000 и в нынешнем году до 20 000, из которых теперь 16 000 человек наряжены в крымский поход; им велено в начале апреля быть у Царицынки в полном числе, но мы уже прошли 300 верст от Царицынки, а Козаков гетманских при армии только 12 730 человек, и половина их на телегах едут, и отчасти плохолюдны, отчасти худоконны, большую часть их мы принуждены возить с собою, как мышей, которые напрасно только хлеб едят. Напротив того, запорожцы из того же народа, беглые из той же Украины, на каждого человека по 2 и по 3 хороших лошади имеют, сами люди добрые и бодрые, хорошо вооруженные; с 3 или 4 тысячами таких людей можно было бы разбить весь гетманский корпус».
Армия Миниха шла в Крым по пути Леонтьева, по правому берегу Днепра, на расстоянии 5—50 км от реки.
7 мая русские войска впервые увидели татар. Их было около ста. Казаки кинулись им навстречу, но никого не захватили. На другое утро более значительный неприятельский отряд подошел к правому крылу армии и удалился, даже не связываясь с казаками.
9 мая фельдмаршал велел выступить пяти отрядам, каждый из которых состоял из 400 драгун и 500 казаков. Так как местность представляла собой обширную равнину, то отрядам велено было идти интервалами, имея друг друга в виду, и присоединиться к тому отряду, который будет ближе к неприятелю. Всеми отрядами командовал генерал Шпигель. Не прошли они и восьми километров, как встретили отряд из 200 ногайских татар, которые, заметив русских, немедленно бежали. Казаки нагнали их, нескольких побили, двоих взяли в плен. Имея приказание придвинуться на самое близкое расстояние к неприятелю, Шпигель не успел пройти еще 8 км, как должен был быстро собрать все отряды. Навстречу ему шел корпус в 20 тысяч человек. Генерал только что успел образовать из драгун каре и спешить переднюю шеренгу, как неприятель окружил его со всех сторон. Татары с гиком напали на русских и засыпали их стрелами. Драгуны не смешались, стреляли не торопясь, только когда были уверены, что не промахнуться. Такой отпор так подействовал на татар, что они не смели подойти к каре ближе чем на сто шагов. Окружив отряд, они сделали несколько ружейных выстрелов и пустили много стрел. Узнав об опасности, которой подвергался генерал Шпигель, Миних во главе трех тысяч драгун и двух тысяч казаков отправился с генералом Леонтьевым выручать его. За ним следовали полковник Девиц с 10 гренадерскими ротами и пикет от всей пехоты. Татары, завидев их, поспешно удалились, оставив на месте 200 убитых. В этой атаке, продолжавшейся более шести часов, Шпигель потерял 50 человек убитыми и ранеными. Сам он и полковник Вейсбах были ранены стрелами.
Первое сражение сильно подняло боевой дух русского войска и, соответственно, вызвало страх у татар перед регулярными войсками.
Во время сражения крымский хан со всей ордой численностью около 100 тысяч всадников стоял в 80 км. Узнав об исходе боя, хан ушел за Перекоп.
18 мая русская армия подошла к 7-километровой линии Перекопских укреплений. Миних был неприятно удивлен: казаки ему сообщили, что «валы везде осыпались, так что местами верхом и в телегах переехать можно». А на самом деле что ров оказался очень глубок, склон крут, как каменная стена, бруствер по всему валу сделан новый и построены башни.
Тем не менее фельдмаршал решил штурмовать Перекоп. Но для начала Миних написал хану, что он послан императрицей для наказания татар за их частые набеги на Украину и намерен во исполнение данного ему приказания предать весь Крым разорению. Но если хан и его подданные намерены отдать себя под покровительство ее величества императрицы, впустить в Перекоп русский гарнизон и признать над собой владычество России, то он, фельдмаршал, немедленно вступит в переговоры и прекратит враждебные действия. Первым же условием Миних требовал сдачи Перекопа. В ответ на это письмо 20 мая хан поручил мурзе объяснить графу Миниху, что война не была объявлена и поэтому его удивляет это нападение в его собственном государстве, что крымские татары не вторгались насильственным образом в Россию, вероятно, то были ногайцы, народ хотя и пользующийся покровительством крымских татар, однако настолько необузданный, что с ним и справиться никогда не могли. Россия могла бы ограничиться взысканием с них и наказать по своему усмотрению всех, кого бы только удалось захватить, как это и было сделано в прошлом году. А что он, сам хан, так связан константинопольским договором, что не может решиться на разрыв. Что же касается Перекопа, то он не волен над ним, потому что гарнизон, состоящий из турецкого войска, не согласится на сдачу. Впрочем, хан просил прекратить военные действия, предлагая вступить в переговоры, а закончил объявлением, что если на него нападут, то он будет защищаться всеми силами.
Миних понял, что против татар остается только употребить оружие. Он отпустил мурзу с ответом хану, что после его отказа от милости императрицы и от предлагаемых мер покорности он увидит опустошение страны и пылающие города, что, зная вероломство татар, он не может им верить, когда они предлагают переговоры. После отъезда мурзы армии было велено готовиться к наступлению.
С восходом солнца полки встали под ружье. В лагере оставлены были больные и по десять человек из каждой роты для охраны обозов. Армия, взяв направление направо, шла шестью колоннами.
Тысяче солдат было приказано провести демонстративную атаку перекопских позиций на правом фланге. Турки поддались на уловку Миниха и сосредоточили на этом участке значительные силы.
Наступление же основных сил стало для турок неожиданностью. На счастье русских ров оказался сухим. Солдаты, спустившись туда, с помощью пик и штыков, помогая друг другу, стали взбираться наверх. Между тем артиллерия не переставала громить бруствер. Увидев, что дело принимает серьезный оборот, татары не дождались появления русских наверху бруствера и обратились в бегство, бросив свой лагерь.
Русские быстро форсировали ров и бруствер, но башни Перекопской линии продолжали стрельбу. Одну из башен штурмом взял капитан Петербургского гренадерского полка Кристоф Манштейн с 60 солдатами своей роты. Несмотря на огонь противника, гренадеры топорами прорубили дверь в башню и ворвались туда. Капитан предложил сдаться противнику. Турки согласились и стали быстро складывать оружие, как один из гренадеров ударил штыком янычара. Взбешенные этим поступком, турки снова взялись за сабли и стали защищаться. Они убили шестерых гренадеров и ранили 16, в том числе и капитана. За это все 160 янычар, охранявших башню, были заколоты. Гарнизоны остальных башен поступили умнее: все вовремя бежали вслед за татарами.
Штурм перекопских укреплений обошелся русским в одного убитого офицера и 30 солдат, ранены 1 офицер и 176 солдат.
Сама же перекопская крепость держалась до 22 мая, когда паша согласился сдаться с тем, чтобы туркам было позволено свободно покинуть крепость и уйти к крымскому хану. Первоначально Миних хотел, чтобы паша сдался военнопленным, но после его отказа и еще нескольких переговоров ему дали обещание, что его проводят до первой приморской пристани, откуда он со своими людьми должен отплыть в Турцию. С паши взяли слово, что он в течение двух лет не будет участвовать в войне против России. Однако русские нарушили условия. По выходе коменданта с гарнизоном в 2554 человека из крепости с ним поступили как с военнопленным. На его претензии отвечали, что Порта и хан, в противоположность условию последнего трактата, задержали 200 человек русских купцов и поэтому, пока их не выпустят, пашу не освободят.