Подойдя к реке Кальмиусу, авангард встретил трех казаков, объяснивших, что они принадлежат корпусу генерала Шпигеля, который шел на Бахмут, но казаки сбились с пути и теперь ищут, как бы соединиться с ним. Фельдмаршал не поверил казакам, велел их задержать и продолжать идти. На другой день привели других казаков, которые повторили сказанное первыми и прибавили, что фельдмаршал Миних со своим корпусом выступил из Крыма и направился на Украину. Это известие заставило Ласси повернуть назад. В начале октября 1736 г. корпус Ласси прибыл в Изюм.

20 апреля 1736 г. Миних выступил из Царицынки с армией численностью около 54 тысяч человек. Войска были разделены на пять колонн. Генерал-майор Шпигель командовал первой колонной, составлявшей авангард. Принц Гессен-Гомбургский вел вторую колонну, генерал-лейтенант Измайлов — третью, генерал-лейтенант Леонтьев — четвертую и генерал-майор Тараканов — пятую.

Полкам раздали запас хлеба на два месяца, и офицерам приказано было взять с собой, по крайней мере, столько же. Фельдмаршал хотел бы снабдить войско и большим запасом провизии, так как ее было достаточно припасено за зиму но не хватало подвод. Все-таки он не решался откладывать поход, а поручил генерал-майору князю Трубецкому позаботиться о доставке провизии в армию. Но, увы, князь Трубецкой действовал очень медленно, вполне возможно, что со злым умыслом. Отправленные им обозы не составляли и одной десятой от запланированного.

В армии Миниха были как запорожские, так и украинские (гетманские) казаки. О них Миних писал императрице: «В прежние времена гетманские казаки могли выставлять в поле до 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 мая хан поручил мурзе объяснить графу Миниху, что война не была объявлена и поэтому его удивляет это нападение в его собственном государстве, что крымские татары не вторгались насильственным образом в Россию, вероятно, то были ногайцы, народ хотя и пользующийся покровительством крымских татар, однако настолько необузданный, что с ним и справиться никогда не могли. Россия могла бы ограничиться взысканием с них и наказать по своему усмотрению всех, кого бы только удалось захватить, как это и было сделано в прошлом году. А что он, сам хан, так связан константинопольским договором, что не может решиться на разрыв. Что же касается Перекопа, то он не волен над ним, потому что гарнизон, состоящий из турецкого войска, не согласится на сдачу. Впрочем, хан просил прекратить военные действия, предлагая вступить в переговоры, а закончил объявлением, что если на него нападут, то он будет защищаться всеми силами.

Миних понял, что против татар остается только употребить оружие. Он отпустил мурзу с ответом хану, что после его отказа от милости императрицы и от предлагаемых мер покорности он увидит опустошение страны и пылающие города, что, зная вероломство татар, он не может им верить, когда они предлагают переговоры. После отъезда мурзы армии было велено готовиться к наступлению.

С восходом солнца полки встали под ружье. В лагере оставлены были больные и по десять человек из каждой роты для охраны обозов. Армия, взяв направление направо, шла шестью колоннами.

Тысяче солдат было приказано провести демонстративную атаку перекопских позиций на правом фланге. Турки поддались на уловку Миниха и сосредоточили на этом участке значительные силы.