Отношение Менгли-Гирея к Литве начало меняться после того, как в 1502 г. он нанёс решающее поражение большеордынскому хану Шейх-Ахмаду: «Того же лета, Июня, Крымский царь Менгли-Гирей побилъ Шиахмата царя Болшиа орды и Орду взялъ»856
. Разгромленный хан бежал в Литву, но там этого теперь уже бесполезного союзника арестовали и посадили под стражу в Вильне: «И Шигъ-Ахметь и Хозякъ и Халекъ и Алчинъ Тактамышъ, восмь ихъ, въ Киевъ прибегли, и киевский воевода князь Дмитрей поимавъ, ихъ на Вышегородъ ввелъ»857; «Шигъ-Ахметя Александръ король поимавъ, въ Вилне въ Вышегороде держитъ; а братью его инде держитъ»858.Одержав победу над Шейх-Ахмадом, Менгли-Гирей принял титул кагана, употреблявшийся правителями Золотой Орды времён её великодержавия, заявив тем самым свою претензию на то, чтобы стать их преемником: «После 1502 г., когда под натиском Менгли-Гирая окончательно пала Большая Орда – основная наследница Золотой Орды в территориальном отношении, Крымское ханство по военному могуществу выдвигается на первое место „среди равных“ – других татарских ханств, тем самым превращаясь в фактического наследника Золотой Орды, что уже давало Менгли-Гираю полную свободу для широкой пропаганды громкого титула хакан. Например, уже в 907/1502 г., то есть сразу по „горячим следам“ вышеназванного события, он велел на мавзолее около Чуфут-кале выбить следующую надпись: „Эту благословленную, блаженную и изящную гробницу велел соорудить великий хан и хакан знаменитый Менгли-Гирай хан бин Хаджи-Гирай-хан, в 907 году“. В последующем 909/1503—1504 г. он опять повторил это громкое титулование в надписи на ханском дворце: „Этот великолепный вход и эти величественные двери велел соорудить государь двух материков и хакан двух морей, государь сын государя султан Менгли-Гирай-хан бин Хаджи-Гирай-хан“»859
.