В 1505 г., как отмечено в Скарбовой книге Литовской метрики, в Литву пришли послы от "князей Ногайских посполу с тыми, послы заволскими" [Скарбовая книга 1898: 27], т. е. ногайское посольство было отправлено вместе с посольством потомков Ахмеда и Махмуда. Еще ранее, в 1503 г., ногайские послы также приезжали в Литву вместе с послами "царя Заволского" [Акты 1846: 354].
Косвенно о ногайско-астраханском "союзе" свидетельствует и эпизод московско-казанских отношений 1505 г. 24 июня 1505 г. произошел погром русских купцов на ежегодной казанской ярмарке. Московский посол М. А. Кляпик был арестован. Мухаммед-Эмин, правивший тогда в Казани, послал 40 000 казанцев, а также 20 000 ногаев — союзников хана к Нижнему Новгороду. В результате искусной обороны города пленными литовскими солдатами натиск на город был отражен, а ногайский князь — союзник Мухаммед-Эмина погиб в бою [Худяков 1991: 61–62]. Союзнические отношения Казани с ногаями объяснялись родственными связями хана: его женой была дочь мирзы Мусы. Как свидетельствует Холмогорская летопись, некоторые русские, попавшие в плен в Казани летом 1505 г., были разосланы Мухаммед-Эмином "во Асторокан и в Натай" [ПСРЛ 1977: 134]. Таким образом, в это время, вероятно через ногайское посредство, Казань была связана с Астраханью.
О возможности контроля ногаев над Астраханью и позже свидетельствует обращение русского правительства к Алчагир-мирзе (сыну Мусы) в 1507 г.: в памяти русскому посланнику в Ногайскую Орду Чюре содержалась просьба найти и вернуть в Москву некоего Мелеха, находившегося в плену в Астрахани "у Мустофарова Салтанова человека у Абдулы" [Посольская книга 1984: 64].
Видимо, до 1508 г. в Астрахани вообще не было какой-либо стабильной власти (по крайней мере какого-то одного конкретного правителя). В материалах второго несостоявшегося посольства Ивана III к Менгли-Гирею с И. Н. Беклемишевым (февраль 1503 г.) содержалась запись наказа послу. И. Н. Беклемишеву следовало говорить, что в тот год "царевичя и азтороканских царей люди" на Дону "посла нашего Александра, которого есмя посылали к кафинскому салтану, да и его посла Алакозя пограбили и людей наших торговых да и турков многих до смерти побили, а иных поймав, свели, а рухляди у них много поймали. И где было тебе за то на азтороканских царей и царевичев со мною стояти содинова, и ты их людей у нас просишь, а яз их держу того деля: хочу свое взяти" [РИО 1884: 462]. В этом документе потомки Ахмеда и Махмуда впервые названы астраханскими царями. Через несколько лет, в октябре 1508 г., Менгли-Гирей писал великому князю Василию, называя их так же: "И нынеча кто мне недруг, то и тебе недруг: астороханские Ахметевы и Махмутовы дети цари, Бог даст, как весна станет, поискать нам их…" [РИО 1895: 19].
Таким образом, мы весьма условно относим начало самостоятельного правления хана Абд ал-Керима в Астрахани к 1508 г.
Планы завладеть Астраханью не оставляли Менгли-Гирея вплоть до его смерти. Астрахань как наследница Большой Орды продолжала оставаться смертельным врагом Крыма. В сентябре 1508 г. Менгли-Гирей в письме великому князю Василию просит у него 10 труб ("да поделаны бы были к ним и ножны") для будущего астраханского похода [РИО 1895: 26].
Для окончательной победы над Астраханью Менгли-Гирей нуждался в помощи Москвы, прежде всего для блокирования города с Волги судами. Именно при Менгли-Гирее в Крыму возникает идея использовать московскую судовую рать для борьбы с Астраханью. Важность участия Москвы в этой акции оценивалась очень высоко. Один из крымских сановников, Баба-ших, в октябре 1508 г. писал Василию о Менгли: "Толко азстараханское дело учинишь, и он тебя и до смерти не останет, на том роту и правду учинил, той речи прямы… Воевав Азторохань, и после и наш и твой недруг король, оба нас вместе, молвит царь, умнем его воевати, как жито поспеет" [РИО 1895: 38–39].