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