В августе 1735 года Миних переправился через Дон и остановился в Новопавлопске. Здесь 29 августа получил он высочайший указ, в котором отдавалось на его волю - начать ли осаду Азова нынешнею же осенью или отложить до весны, а зимою держать крепость в тесной блокаде. Миних отвечал, что избирает последнее, но, чтоб не терять времени, немедленно отправится к украинской линии в местечко Кишенки к тамошней армии, чтоб с нею предпринять поход на Крым: время для этого самое благоприятное, потому что татары перебрались на кубанскую сторону для персидского похода. В это время Миних избавился от неприятного ему человека: умер командовавший Украинскою армиею генерал Вейсбах, на которого возложена была крымская экспедиция: он считал себя старше фельдмаршала и потому не хотел подчиняться ему. Жалуясь на Вейсбаха, Миних писал, что генерал Леси, который также старше его, никогда не предъявлял подобных претензий.
В сентябре, находясь в Полтаве, Миних и вся свита его занемогли местною лихорадкою, но болезнь не помешала фельдмаршалу распорядиться отправлением в Крым генерал-лейтенанта Леонтьева с 22000 регулярного и 26000 иррегулярного войска (но собственно Леонтьев мог выступить только с 39795 человеками). Уведомляя об этом императрицу, фельдмаршал писал: "Если крымская экспедиция окончится благополучно, то пленных христиан, которых там считают до 20000 семейств, куда прикажете отвозить для поселения?" Леонтьев выступил в поход 1 октября от реки Орели по направлению к реке Самаре. От постоянной засухи вода в степных реках была очень низка, и войско переправлялось чрез них беспрепятственно, но на случай поднятия воды к обратному пути солдаты все же строили мосты. Сам Миних переехал из Полтавы в местечко Царицынку, лежащее на границе, где предполагал оставаться до тех нор, пока приведет в безопасное состояние сообщения и постирунги вплоть до Перекопи, чтоб войско могло иметь надежный обратный путь. 6 октября Леонтьев стоял на речке Вороне, а на другой день достиг речки Осакоровки, где местами степь летом была выжжена татарами, однако уже поднялась молодая трава, и армия в дровах, воде и конском корме нужды не терпела. У реки Конские Воды русские напали на аулы ногайских татар, убили более тысячи человек, захватили с лишком 2000 штук рогатого скота, 95 лошадей, 47 верблюдов. "Причем, - писал Миних, - наше войско со всякою бодростию поступило, и никому пощады не было". Этим делом и ограничился поход: с 13 числа начались дожди, потом снег, крепкие морозы, и. 16 числа на урочище Горькие Воды Леонтьев собрал военный совет, на котором предложил вопрос: идти ли далее или возвратиться? Ответ был, что надобно возвратиться, потому что уже пало около 3000 лошадей: схваченные татары и возвратившийся из Крыма прасол объявили, что далее лесу и воды пет, до Перекопи еще десять дней пути и в это время при такой погоде все лошади перемрут.
Миних сильно досадовал на возвращение Леонтьева ни с чем, тем более что это была его мысль идти в Крым осенью, после уборки хлеба, но делать было нечего. В ноябре он вызвал в Царицынку запорожского кошевого Милашевича с другими знатными козаками для совещаний о будущем походе. Фельдмаршал спрашивал их, в каком числе они могут собраться к походу. Запорожцы отвечали, что войско их ежедневно прибывает и убывает и потому о числе его подлинно показать никак нельзя, надеются, однако, собрать до 7000 человек, хорошо вооруженных, но не все будут на конях. Потом, спрошенные, каким образом и в какое годовое время, но их мнению, удобнее идти в крымский поход, запорожцы отвечали: армия должна выступить в поход 10 апреля от реки Орели, потому что в это время в степи от недавних снегов и дождей еще не может быть нужды в воде, трава везде в полном росту и неприятелем сожжена быть не может, также по пашням озими весною способны быть могут; в Крыму нынешним летом был урожай, следовательно, и там армия в хлебе нуждаться не будет, ногайцы против регулярного войска не устоят, и русская армия беспрепятственно войдет в Крым: перекопские укрепления остановить ее не могут.
Серьезная война еще не начиналась, а уже генералы перессорились. Миних оставил войска в Польше под начальством генерал-фельдцейгмейстера принца гессен-гомбургского, который должен был выводить их на Украйну. Фельдмаршал был недоволен некоторыми его распоряжениями и выразил свое неудовольствие в письме к нему; принц отвечал: "Что, ваше графское сиятельство, в наставление мне писать изволите, чтоб впредь того не чинить: и за оное (хотя при моих летах знаю, что чинить надлежит) вашему сиятельству благодарствую; однако притом доношу, что я уже имею честь быть в службе ее величества четырнадцать лет, а еще того не чинил, чтоб ее величеству противно было, и того не надеялся, чтоб я от вашего графского сиятельства за то, что к лучшей пользе интересов ее величества чинил, мог реприманды получить, и весьма чувствительные, и прошу меня оными обойти".