В 1771 году настала очередь Крыма, который подвергся вторжению с обоих флангов — через Перекопский перешеек и со стороны Керченского пролива. Территория полуострова была полностью захвачена. Повсюду воцарился крайний беспорядок, усиленный внутренними конфликтами между татарами и турками. Турецкий губернатор был взят в плен; хан позорно бежал, даже не сделав попытки оказать сопротивление, тем самым лишив татар последнего источника власти. Двоим его сыновьям была обещана независимость полуострова под покровительством России, и они с большой свитой отправились в Санкт-Петербург, чтобы там дать клятву верности императрице Екатерине. Таким образом, Османской империей была утрачена большая часть северного побережья Черного моря, за исключением крепостей Очакова и Кинбурна. В то же самое время в районе Кавказа русские изгнали турок из Мингрелии и Грузии.

Теперь Австрия и Пруссия стали проявлять озабоченность из-за продолжающихся завоеваний их могущественного русского соседа и предложили царице свои посреднические услуги в деле установления мира с Портой. Екатерина, однако, ответила, что она будет вести переговоры только с самим султаном, без вмешательства других стран. Последовал период сложных дипломатических маневров между европейскими державами и Турцией, затрагивавших также вопросы «дележа добычи» в планировавшемся разделе Польши. Порта предвидела союзы с Австрией и Францией в обмен на поддержку против России. Наконец, уже к завершению кампании 1771 года, Россия и Порта согласились на перемирие, за которым последовало обсуждение условий мирного договора сначала в Фонтанах, а затем в Бухаресте.

Переговоры потерпели неудачу в значительной степени потому, что муфтий и вся улема воспротивились передаче Крыма, как мусульманского государства, находившегося под властью султана-халифа, под протекторат христианской державы. Хотя султан Мустафа, с великим визирем и главными министрами, не возражали против предложенных условий, султан был вынужден отвергнуть их из-за опасений, что улема поднимет в Стамбуле восстание. В результате после более чем годичного перерыва война была возобновлена. Воспользовавшись передышкой, султан восстановил на посту великого визиря Мухсинзаде-пашу, освободителя Мореи.

Реорганизовав и укрепив армию, он, как мог, воодушевил ее и в 1773 году начал новую кампанию, на этот раз ограниченную южным берегом Дуная и районом Болгарии, от двух крепостей — Силистрии и Рущука — до берегов Черного моря. Сначала турки выдержали осаду русскими Силистрии, сражаясь за каждую улицу и заставив их отступить. За это русские отомстили массовым убийством гражданских жителей незащищенного городка Пазарджик. Застигнутые врасплох за этим занятием появившимся подразделением турок, русские поспешно отступили, оставив на кострах в своем лагере котлы с наполовину сваренным обедом. Тем временем другой русский отряд двинулся на Варну, но его наступление было успешно отражено турками с помощью отряда моряков с турецкой морской эскадры, крейсировавшей в тот момент вдоль побережья Черного моря.

Вдохновленные этой чередой неожиданных успехов, турки в 1774 году возобновили наступательные действия от своей штаб-квартиры в Шумле, которая господствовала над долиной Дуная, начинавшейся от подножия Балканского хребта. На этот раз они двинулись вниз по течению в направлении устья реки с целью вытеснить противника из крепости Хиршова (Хыршова). Но русские атаковали первыми, полностью разгромив крупную турецкую армию, захватив ее лагерь со всем имуществом и оставив турок с силами, совершенно недостаточными для обороны Шумлы. Оказались под угрозой пути сообщения со Стамбулом, так как русские, стремившиеся окружить турок, двинулись на юг в направлении проходов через Балканы.

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

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

В то же время удержание Россией двух ключевых крепостей — Керчи и Еникале, а также городов Азов и Кинбурн создавало для них сильный плацдарм в Крыму и в прилегающих областях, а значит, и средство для захвата Крыма в любое время, когда они пожелают. Но самое главное заключалось в том, что это давало российскому флоту доступ в Черное море, иными словами, то, что Россия добивалась со времен Петра Великого, почти сто лет назад. Никогда больше Черное море уже не будет оставаться исключительно, «чисто и нерушимо», османским озером. Согласно договору Россия получила право навигации в его водах. На основе взаимности это право распространялось на прибрежные воды обеих держав и предполагало русское консульское присутствие в тех частях Османской империи, где затрагивались интересы России.

В Средиземном море русский флот должен был покинуть Греческий архипелаг. В Азии Порте были возвращены Грузия и Мингрелия. То же самое касалось румынских провинций Валахия и Молдавия. Но в этом случае делалась одна существенная оговорка. Здесь не только должно было гарантироваться справедливое правление и свобода вероисповедания для христианского населения, но и право русских на вмешательство от его имени через русских послов, аккредитованных в Порте. Это подразумевало право защиты, которое русские позже расширили на всех христианских подданных империи, открыв путь к зловещим конфликтам в будущем. Помимо этого, русские подданные должны были иметь свободный доступ, как паломники, к святым местам Палестины, без уплаты подушного налога и под защитой османских законов.

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

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