Но Азов пришлось возвратить туркам. Крымский хан снова выступил с требованием дани. Снова начались грабительские набеги крымских татар на украинские земли, которые терроризировали население и мешали хозяйственному освоению плодородных, черноземных земель Причерноморья. Россия, занятая Северной войной, не могла пока выделить достаточных сил для активных военных действий на юге. Ликвидацию последышей Золотой Орды — крымских ханов — пришлось отложить на вторую половину XVIII столетия. Это можно было сделать, только вытеснив из Северного Причерноморья Турцию. Крымский вопрос решался в войнах с Турецкой империей.
Несмотря на неудачу Прутского похода, именно при Петре I были созданы условия для успешной борьбы с Крымским ханством и поддерживавшей его Турцией. Важнейшим из них было создание регулярной армии.
Регулярная армия, созданная Петром I, комплектовалась путем рекрутских наборов и имела стройную организацию, делилась на дивизии, бригады, полки. Старые неудобные и тяжелые пищали были заменены кремневыми ружьями с трехгранными штыками. Значительно усилилась артиллерия. За первую четверть XVIII в. русские оружейные заводы выпустили более 3500 пушек. Особенно важную роль в войнах с крымскими татарами играла многочисленная и хорошо вооруженная кавалерия. Кавалеристы русской армии имели укороченные ружья, пистолеты, палаши или сабли; в каждом кавалерийском полку была своя конная артиллерия.
Специально для борьбы с Крымским ханством была создана милиция из украинского населения, усилены казацкие полки. В 1725 г. общая численность армии достигала 320 тыс. человек, в том числе около 130 тыс. человек в полевой армии. Петровский «Устав воинский» определял тактику боя, обучение солдат проводилось в соответствии с тогдашним уровнем развития военной науки.
Все это обеспечивало русской армии важные преимущества в войнах с крымской конницей, вооруженной только холодным оружием и луками, и с турецкими войсками. Однако борьба с Крымом и Турцией была трудной и продолжительной.
Достигнутый дорогой ценой — ценой уступки крепости Азов — мир с Турцией не принес спокойствия южной границе России. Набеги крымских татар продолжались, несмотря на «ферманы» турецкого султана о перемирии. Наместник турецкого султана доносил из Азова: «После заключения с московским царем мира татарскому войску и пограничным жителям было строго наказано впредь не делать набегов. Но татары, не повинуясь наказу, пошли производить грабежи по дорогам к Астрахани». Когда азовский паша по жалобе русских воевод послал против своевольников отряд янычар, пограничная турецкая стража не только не поддержала их, но даже постаралась воспрепятствовать походу, заявив: «Мы живем татарскою добычею, на этих границах ферманы не исполняются!» Обезопасить южные области можно было, только окончательно сокрушив Крымское ханство.
В 1735 г. большое крымское войско во главе с самим ханом выступило в поход против Персии. Путь его проходил по русским владениям на Северном Кавказе. Здесь произошло несколько серьезных столкновений крымцев с русскими войсками. В качестве ответной меры русское правительство начало готовить поход на Крым. Для похода было сосредоточено около 40 тыс. войск под командованием генерал-лейтенанта Леонтьева. Одной из целей похода было освобождение русских пленных, которых было много в Крыму. Фельдмаршал Миних писал по этому поводу в Москву: «Если крымская экспедиция окончится благополучно, то пленных христиан, которых там считают до 20 000 семейств, куда прикажете отводить для поселения?» Но и этой ограниченной цели — освобождения пленных — не удалось достигнуть. Русское войско дошло до реки Конские Воды, разгромило там ногайских татар, захватило стада, но продвинуться дальше не сумело. Начались сильные дожди, затем — неожиданно ранние морозы и снег. Корма не хватало, в обозе и коннице пало около 3 тыс. лошадей. Поход пришлось прекратить, не достигнув Перекопа.
Весной 1736 г. началась война с Крымом и Турцией. Сначала отряд русского войска (до 25 тыс. человек) осадил крепость Азов. Этот поход должен был отвлечь турецкие войска от Крыма: «Силы неприятельские разделились бы, для крымской экспедиции немалая польза». Главные силы во главе с фельдмаршалом Минихом в апреле начали поход на Крым. Учтены были ошибки прошлого похода, когда русское войско страдало от недостатка продовольствия и воды. В степи была свежая трава, которую татары не могли по своему обыкновению поджечь впереди русского войска. На этот раз 54-тысячная русская армия с артиллерией и обозами успешно преодолела степи и подступила к укрепленной перекопской линии.