Вскоре после успешного окончания осады Ираклиона, положившего конец долгой Критской войне, наступило затишье. К лету 1670 года Фазыл Ахмед-паша вернулся в Стамбул, а спустя два года он снова выступил во главе своей армии, но на сей раз в направлении Украины. К этому времени польско-литовская Речь Посполитая уже значительно ослабела, и казачьи волнения, которые начались в 1648 году, к 1654 году переросли в войну между Речью Посполитой и Московией, которая должна была решить вопрос суверенитета Украины. Речь Посполитая подвергалась нападениям со всех сторон, в том числе и со стороны Швеции, прежде чем многолетние спорадические столкновения закончились в 1667 году тем, что Украина была разделена по течению Днепра, причем Правобережье, то есть ее западная часть, оказалась под властью Речи Посполитой, а Левобережье, то есть восточная часть, попала под контроль московитов. Украинские казаки предпочитали быть независимыми и от Речи Посполитой и от Московии, а гетман Петр Дорошенко, который был вожаком казаков Правобережья, пытался заручиться поддержкой Османской империи. В июне 1669 года, после нескольких месяцев переговоров, с целью определить, является ли Дорошенко искренним в своем желании подчиниться Османской империи, султан направил ему символы, которыми по традиции вознаграждались вассалы империи (штандарт в виде конского хвоста, барабан, знамя и свидетельство о введении в должность) в знак признания власти гетмана над всей Украиной. Спустя почти двадцать лет после того, как Богдан Хмельницкий впервые выразил желание стать «рабом султана», значительная часть Украины снова оказалась под властью Османской империи.

Казалось, что прямая поддержка казаков Правобережья даст империи еще одного союзника в степи, помимо уже имевшихся татар. Решив оказывать поддержку казакам в их борьбе против Речи Посполитой, турки отказывались от своей традиционной политики в этом регионе, состоявшей в сохранении баланса между Речью Посполитой и Московией. В 1671 году Речь Посполитая ответила тем, что направила в Правобережную Украину силы под командованием гетмана Яна Собеского, тем самым бросив вызов султану. В свою очередь, турки объявили войну, сославшись в качестве casus belli[36] на то, что поляки вторглись во владения их нового вассала. Целью Османской империи был захват стратегической крепости Каменец-Подольский, находившейся в провинции Подолия и расположенной на крутом утесе, который возвышался над тесниной, образованной течением одного из притоков Днестра. Эта считавшаяся неприступной крепость должна была стать опорным пунктом, необходимым для более плотного контроля северных рубежей империи. Потенциальную выгоду сулило и то, что за часто выходившими из подчинения вассальными государствами Молдавия и Валахия можно было установить более пристальное наблюдение.

С самого начала XVII столетия уделом принцев Османской империи была замкнутая жизнь во дворце Топкапы, но Мехмед твердо решил, что его старшему сыну и наследнику следует знать, что ожидают от султана. Эта новая военная кампания давала возможность продемонстрировать, что Османская империя все еще может вступать в войну с целью расширения своих территорий и вести ее под командованием монарха-воителя, и поэтому султан решил лично возглавить свои войска, взяв с собой принца Мустафу, а вместо своей матери, Турхан Султан, он взял мать Мустафы, свою любимую наложницу, Рабию Гюльнуш Эметуллах.[37]

Поход на север, в Польшу, проходил в дождливую погоду и был рискованным предприятием. Во время одного перехода серебряная карета, в которой ехала Рабия Гюльнуш Эметуллах, быстро увязла в глинистой почве, и великому визирю пришлось ее спасать. Принц Мустафа и его мать остались южнее Дуная, в Бабадаге, тогда как султан со своей армией продолжили движение и подошли к Исаккее, где был построен мост через Дунай. Прежде чем переправиться на северный берег, Мехмед ненадолго вернулся в Бабадаг, чтобы навестить свою семью. Спустя тридцать девять дней и находясь в четырех или пяти часах от своей цели, крепости Каменец, армия переправилась через Днестр и вступила на польскую территорию. Крепость была слабо защищена, и 27 августа 1672 года она пала после девяти дней интенсивного артиллерийского обстрела. Когда ключи от нее были переданы Фазыл Ахмед-паше, султан смог осмотреть это последнее завоевание Османской империи. Он приказал Абдурахман Абди-паше, который во время боевых действий находился в безопасности, сочинить памятную поэму из двадцати четырех двустиший и хронограмму. Обычно такую поэму потом выбивали на мраморной доске и выставляли на всеобщее обозрение, установив над воротами крепости.

Защитникам Каменца сохранили жизнь, имущество и даровали право остаться жить в стенах крепости, если они того пожелают, а также право отправлять свои собственные религиозные обряды, будь то католичество или православие. Им также было позволено содержать столько церквей, сколько им нужно. Как обычно, некоторое количество церквей превратилось в мечети — католический собор Святых Петра и Павла стал мечетью султана Мехмеда IV, другие были названы в честь его матери Турхан Султан, Рабии Гюльнуш Эметуллах, великого визиря Фазиля Ахмед-паши, Мусахиба («Собрата») Мустафа-паши, а также Мерзифонлу Кара Мустафа-паши, второго и третьего визиря соответственно. Прошло совсем немного времени и стали очевидны другие приметы нового режима, так, например, были учреждены типичные для мусульманского города благотворительные фонды. В первую пятницу после завоевания воин-султан произвел церемонию пятничной молитвы в своей новой мечети.

Новая османская провинция Каменец (или, если быть точным, Камениче), образованная на основе провинции Подолия, входившей в состав Речи Посполитой, оказалась, как и другие провинции, сформированные в годы пребывания у власти клана Кёпрюлю (Варад, Уйвар и Крит), несколько меньше, чем провинции, образованные в первые столетия османского завоевания, когда было легче делать крупные территориальные приобретения. Еще до конца 1672 года, в целях налогообложения, в Каменце был проведен опрос жителей, и новая администрация города попыталась ввести систему землевладения, с помощью которой земельными участками вознаграждались кавалеристы в обмен на то, что они примут участие в военных действиях, когда это потребуется. Раньше эта система применялась во всех центральных регионах империи, но затем была временно отменена. Хотя даже в отличавшихся большей статичностью боевых действиях конца XVII столетия кавалерия не утратила своей эффективности, но на самом деле это был век пехоты, и применение такого старого и почитаемого рода войск в Каменце и других завоеванных в то время провинциях скорее воспринимается как попытка воссоздать золотой век империи, а не как стремление справиться с военными проблемами.