И тут представился весьма удобный случай – как раз накануне османо-австрийской войны валашский господарь Михай и молдавский господарь Аарон восстали против турецкого владычества, и, вторгнувшись на их территорию, крымский хан действовал одновременно и в интересах султана, восстанавливая его законное владычество над отпавшими землями, и в собственных, надеясь получить в благодарность от османского падишаха возможность самостоятельно назначить местного правителя либо предложить султану для утверждения выбранного ханом кандидата. Военная фортуна, казалось, благоволила к своему любимцу, и уже осенью 1595 г. хан рапортовал в Стамбул, что Молдова полностью покорена им, надеясь при этом, что султан проявит благосклонность и назначит местным правителем Адиля Герая, сына нурэддина Вахта.
Этого, однако, не случилось – весь политический расчет крымского хана сломала смена султана – еще в январе 1595 г. вместо благоволившего Гази ІІ Гераю почившего Мурада ІІІ (1574–1595 гг.) османский престол занял его сын, жестокий Мехмед ІІІ (1595–1603 гг.), приказавший при восхождении на престол убить 19 своих братьев, чтобы обезопасить себя от заговоров с их стороны. Новый султан уже не был столь благосклонен к крымскому хану, как его отец, и последовал совету визирей не отдавать Молдову в управление представителю династии Гераев.
Хана настолько расстроило присланное из Стамбула извещение о решении, что он даже отказался от борьбы за Молдову с польским королем Зигмундом III, пытавшимся утвердить здесь своего ставленника Иеремию Могилу. Гази Герай неожиданно для соперников признал последнего законным правителем при условии выплаты обычной дани Крымскому ханству и отправился домой. Султанский отказ явно показал крымскому правителю, что его непоколебимое прежде положение в Османской империи оказалось отныне под угрозой и следует готовиться к борьбе за власть над самим Крымским Юртом. К этому его подталкивали недобрые слухи об интригах, которые плели в Стамбуле его недруги, обвиняя хана в связи с врагами Турции. Главным недоброжелателем Гази Герая в османском правительстве стал Синан-паша, уже ранее пытавшийся приписать все заслуги в войне в Венгрии, принадлежавшие крымскому хану, лично себе и своему сыну.
Продолжая на словах подчиняться Мехмеду ІІІ и даже отправив в 1596 г. сражаться в Венгрию часть крымских войск во главе с калгой Фетхом Гераем, Гази Герай начал готовиться к борьбе за власть над Крымом. Синан-паша не замедлил склонить присланного калгу к принятию ханского достоинства, и хотя Фетх Герай пытался поначалу отказаться, но в итоге был возведен на ханство, а Гази Гераю была дана отставка. Произошедшее показало, что опасения «Боры» были не напрасны, и он принялся создавать настоящую антитурецкую коалицию, призванную не только сохранить за ним крымский юрт, но полностью изменить расклад сил в Центральной и Восточной Европе. При этом он показал себя не только гениальным полководцем, но и тонким расчетливым дипломатом. Крымский хан разослал всем соседним правителям – королю Польши, австрийскому императору, господарям Молдовы, Валахии и Трансильвании и даже запорожским казакам письма, в которых сообщал, что отныне разрывает какие бы то ни было отношения со Стамбулом и приглашал всех совместно выступить против Турции.
Некоторый зазор во времени в пользу Гази Герая возник благодаря внезапной отставке его недоброжелателей в османском правительстве и приходе к власти новых чиновников, убедивших Мехмеда ІІІ не смещать не единожды доказывавшего свою верность и полезность на поле боя крымского правителя. Выйти из затруднительной ситуации, когда султанские документы, подтверждавшие их права на крымский престол были одновременно и у Фетха Герая, и у Гази Герая помогло судебное решение кефинского муфтия, признавшего законным правителем Гази Герая.
Фетх Герай удалился, но не смирился и попытался было летом 1597 г. захватить Бахчисарай, воспользовавшись отсутствием на полуострове законного правителя. Однако отбывший к низовьям Днепра Гази Герай, узнав об этом, вскоре вернулся со всем войском, не оставив мятежнику никаких шансов. Когда тот попытался искать у брата милости, то был зарублен, а затем были казнены также его сторонники и сыновья. Вот как описывают эту казнь источники: «При отправлении Фетха Герая к Высокому Порогу некоторые недальновидные дураки настояли, чтобы он пошел к хану и простился с ним. Он так и сделал: в местечке Накш-Элван близ Каффы он явился к хану и, по обычаю, сняв со своей злополучной головы колпак, стал тереть свое лицо о ханскую полу. В это время отряженные к его умерщвлению убийцы из мансурских эмиров стали бить его без милосердия дубиною и сделали одежду жизни его рубиноцветной от крови». Историк Наима писал: «Фетха Герая вытащили из присутствия ханского несколько татарских мурз из свиты хана, собравшихся возле дверей. Один из них ударил несчастного дубиною по голове, а прочие саблями покрошили его на мелкие части».