У квітні 1515 р. помер Менґлі-Ґерай І, людина, яка перетворила колись невеличку й малозначущу Кримську державу на вагомий суб’єкт міжнародних відносин Східної, а подекуди й Центральної та Південної Європи. Новим ханом стає його син Мехмед-Ґерай І. Прихід до влади Мехмед-Ґерая, відомого своїми антимосковськими поглядами, давав надію Сигізмунду І на успішне продовження литовсько-кримського співробітництва, особливо з урахуванням тієї складної ситуації, в якій опинився новий хан.

Виступаючи продовжувачем зовнішньої політики батька, Мехмед-Ґерай І намагався послабити вплив Москви на середній і нижній Волзі з метою підпорядкування своїй владі цього регіону. Проте новий кримський правитель не мав жорсткої влади над своїми підданими, як це було за Менґлі-Ґерая І. В опозиції до хана перебувала частина його рідних. Основним же конкурентом у боротьбі за владу виступав брат Ахмат-Ґерай, який до того ж обіймав посаду калги.

Крім того, Османська імперія, у васальній залежності від якої Кримський ханат перебував з другої половини 70-х рр. XV ст., якраз підтримувала антиханську опозицію і виступала проти зовнішньої політики Мехмед-Ґерая І. Така позиція Османів пояснюється, по-перше, особистою неприязню між султаном Селімом І і ханом. Ця ворожнеча між ними виникла в ті часи, коли Селім, виступивши проти свого батька — султана Баязида II, звернувся по допомогу до Менґлі-Ґерая І, тоді Мехмед-Ґерай пропонував видати Селіма. А по-друге, зовнішньополітичні плани Криму не тільки не відповідали зовнішньополітичному курсу Стамбула, а навіть суперечили йому. Справа в тому, що османи, докладаючи надзвичайних зусиль до захоплення південно-східної Європи й підпорядкування собі Угорщини та Молдавії, змушені були вести часті й тяжкі війни з європейськими країнами. У цьому протистоянні Корона Польська й Велике князівство Литовське виступили ворогами турків.

Ягеллони підтримували (добре чи погано) угорців і молдаван в їхніх війнах проти турків. Останні, не маючи достатніх сил для прямої агресії проти Польщі й Литовської держави, як ефективний засіб боротьби з ними використовували Кримський ханат, війська якого своїми руйнівними нападами відволікали литовсько-польських Ягеллонів від південно-європейських справ. Зрозуміло, що антилитовська політика Москви була вигідною для Османської імперії.

Весь вищезазначений політичний розклад призвів до того, що султан і московський князь ставили на Алмат-Ґерая, який позиціонував себе як ворог Вільна і Кракова. Тим паче, що території його улусу, а саме межиріччя Дністра та Дніпра, межували з Польським королівством і Литовським князівством. Він навіть просив Василів III допомоги для захоплення Києва. У разі успіху Алмат-Ґерай обіцяв Великому князівству Московському сприяння при «завоюванні Вільна, Троків і цілої Литви». У той же час Василій III, побоюючись литовсько-кримського альянсу, пропонував Селіму І проект угоди проти Великого князівства Литовського та Кримського ханату.

Таким чином, виникла вісь «Стамбул — Ахмат-Ґерай» і «невдоволена ханом кримська знать — Москва», яка була спрямована як проти Литовського князівства й Польського королівства, так і проти Мехмед-Ґерая І. Це автоматично штовхало останнього до зближення з Литвою — Сигізмундом І, тому й не дивно, що саме хан зробив перший крок назустріч. На початку липня 1515 р. з Криму до Києва прибув ханський посол Амрон, який, за словами А. Немировича до ради панів (дорадчого органу вищої литовської знаті), «довідувався про стан господаря нашого [Сигізмунда І] короля його милості, і про вашу милість рад господаря нашого й теж про військо господарське, де б тими часами мало бути». Окрім посла, під Черкаси підійшло двохтисячне кримське військо на чолі з Алп-Ґераєм. Цей царевич вимагав від київського воєводи, аби той надав йому військову допомогу для походу на Московську державу. Причому відмови київського воєводи (мовляв, «коней відігнали козаки білогородські»), через що Немирович не може приїхати, мало цікавили Алп-Ґерая. Він наполягав, щоб воєвода «сам-один приїхав». Казимир Пуласький на основі цього документа дійшов висновку, що якраз тоді й відбувся похід А. Немировича й О. Дашковича спільно з кримцями на Сіверщину. Але, на нашу думку, вчений помилився. Російські джерела, які доволі точно описують усі татарські напади, описують цей похід наприкінці 1514 р. До того ж татарами командував калга Мехмед-Ґерай. Отже, події відбувалися ще за життя попереднього хана.

Поява Алп-Ґерая під Києвом не була випадковою. За великим рахунком, татари не відходили з Київщини після останнього набігу на Сіверщину. Причому, як говорили самі татари московському послу І. Мамонову, Алп-Ґерай разом з Алік-Ґераєм залишились на українських землях Великого князівства Литовського на прохання литовських воєвод, які непокоїлись, що московські війська можуть зробити вторгнення у відповідь на минулорічні напади на Сіверщину. На момент смерті Менґлі-Ґерая І якихось два царевичі стояли на Тясмині неподалік Черкас і новий хан намагався відкликати їх до півострова. Напевно, мова якраз і йшла про цих двох Ґераїв. Тим паче, що в повідомленні за серпень 1515 р. указано вже більш точно, що Мехмед-Ґерай І наказував повернутися саме Алпу і Аліку Ґераям. Небезпечну ситуацію завдяки рішучим і оперативним діям місцевої адміністрації вдалося вирішити з вигодою для Великого князівства Литовського. Корпус Алп-Ґерая було переведено під Мстиславль, звідки він робив напади на Смоленщину. Ідея щодо такого кроку литовської влади належала О. Дашковичу. Московський посланець Михайло Тучков перед цим писав, що саме цей намісник обіцяв татарам провести їх повз Кричів на московські землі.

Невдовзі після згаданого вище демаршу Алп-Ґерая Мехмед-Ґерай І вислав до Литовського князівства велике посольство на чолі з Башибек-мурзою, Ябук-мурзою і таким собі Августином Гарібальдичем. При цьому хан навіть не дочекався повернення аналогічного за рівнем посольства, відправленого до Вільна ще за життя Менґлі-Ґерая І. Офіційним приводом цієї дипломатичної місії було представлення Сигізмунду І нового хана. Також правитель Криму пропонував королю «для вірного братства й вічної нашої приязні між нами докончалними листами списатися й присягами утвердитися потому, як і з батьком його». Велике князівство Литовське і Корона Польська, як і раніше, добре прийняли послів і розмістили їх у передмісті Кракова, але відповідь давати не поспішали. Прибуття Сигізмунда І на початку вересня з Віденського конгресу не принесло змін у цьому процесі. Затримано було й виплату упоминок. Такі дії короля пояснюються тим, що позиції Ягеллонів у Європі дещо стабілізувалися. На конгресі вдалося владнати відносини, хоча й не надовго, з австрійськими Габсбургами і Бранденбургом. У війні з Москвою ініціатива внаслідок нещодавньої оршанської перемоги 1514 р. поступово переходила до литовського боку. У березні 1516 р. король вихвалявся хану, що війська Великого князівства Литовського «часто в землю ворога нашого московського ходять і посполиті землі його шкоди великі роблять і в цілості виходять», і далі додавав, що «люди його [Василія III]) з ласки милого Бога людям нашим в його землі ніде покою не можуть оказати». Та й згадувана вище політична ситуація у Криму давала можливість Вільну і Кракову відчувати себе впевненіше. Тільки в березні 1516 р. до Перекопської Орди було відправлено великого посла Станіслава Скіндера, людину, що мала великий досвід відносин з цим неспокійним сусідом. Скіндер віз до Кіркора умови союзу та упоминки за 1515 р.

Сам факт відправлення посольства ще, зрозуміло, не означав, що переговори дійшли свого логічного кінця. Навпаки, маховик дипломатичної гри між Вільном і Кіркором тільки розкручувався. Шлях до Криму був далекий, та й литовці, судячи з усього, не поспішали. Тож ще у травні Мехмед-Ґерай І із гнівом скаржився Сигізмунду І на відсутність послів: «А до цього часу їх до нас не відпустили». Це зволікання з литовського боку мало свою логіку, а саме — бажання перевірити, наскільки сильними були позиції Мехмед-Ґерая І у Кримському ханаті та чи справді він готовий дотримуватися пролитовського курсу. Не випадково ж в умовах договору було записано, що хан і його сини можуть безпечно приїхати до Великого князівства Литовського й так само безпечно поїхати звідти. На жаль, не відомо, чи це було усне прохання кримського правителя через послів, чи ініціатива литовського уряду, який, зрозуміло, непогано володів інформацією про політичну ситуацію в Криму.

Сам зміст цієї умови вказує на намагання Сигізмунда І повернутися до ординської політики часів Ольгерда й Вітовта, коли татарські хани, включаючи й засновника кримської держави хана Хаджі-Ґерая І, у важкі для себе хвилини переховувалися на території Великого князівства Литовського. Цікаво, що Ахмат-Ґерай, конкурент Мехмед-Ґерая І, заручився аналогічною умовою у московського уряду. Кримський хан, зацікавлений у швидкому підписанні угоди й, зрозуміло, у швидкому отриманні упоминків і неофіційних подарунків, починає тиснути на Сигізмунда І. У березні до Вільна прибуває посланець від Мехмед-Ґерая І Хочжанкул із повідомленням, що ногаї «князь Муслинт, син Чаркгир мурза й інші вісім їх в головах прийшовши... у ноги чолом ударили», тож хан може вже не турбуватися про загрозу з їхнього боку. Крім того, хан через свого гінця вихвалявся, що московський великий князь прислав до нього посла з пропозицією перейти на його бік, але хан залишається вірним дружнім відносинам з Московською державою. Зрозуміло, що це звучало як приховане попередження Сигізмунду І, щоб той поквапився. На це вказує те, що Мехмед-Ґерай І, показуючи свої успіхи й вірність, тут же скаржиться, що він литовських гінців «борзо відпускає», а послів — як батька, так і його — досі не відпустили, ані «того упоминка», обіцяного ще Менґлі-Ґераю І, досі не послали.

Відповідь із Вільна, вислана 29 березня 1516 р., містила загальні фрази, мовляв, король радіє, що ногайці більше не турбують Крим і що хан не вірить московському князю. 24 травня цього ж року з Криму повернувся королівський толмач Лагуш разом із ханським гінцем Кірейга-мурзою. Кірейга привіз новий лист від Мехмед-Ґерая І, у якому кримський правитель, співчуваючи з приводу смерті королеви, знову докоряє Сигізмунду І за те, що той досі не відпустив з Великого князівства Литовського кримських послів і не прислав свого великого посла. Хоча сам Мехмед-Ґерай І, за його словами, відправив своїх послів, «пам’ятаючи присяги наші і правди знайомість даючи». Хан згадував, як відвозив Джелалдина й ходив із синами на Московську державу. Тут же Мехмед-Ґерай І писав, що Василій III прислав до нього свого посла Івана Григоровича Мамонова з пропозицією союзу проти Литовського князівства, причому, за словами хана, московський правитель висунув пропозицію: «Король ваш в рік що упоминків має, і я хочу в рік же вдвоє того посилати». Мехмед-Ґерай І попередив Сигізмунда І, що поки що посадив Мамонова на три ночі в залізо й не відпустить його, «поки від вас брата нашого вість буде», а якщо король хоче й надалі бути в мирі з ханом, нехай швидше присилає послів і упоминок. Друга частина ханського листа стосувалася білгородських татар.