Имея с Россиею выгодный торг, Князья сих многолюдных степных Орд, Шийдяк, Мамай, Кошум и другие, хотели быть в мире с нею, но жаловались, что наши Козаки Мещерские не дают им покоя, тысячами отгоняют лошадей и берут людей в плен; требовали удовлетворения, даров (собольих шуб, сукон, доспехов), уважения и чести: например, чтобы Великий Князь называл их в письмах братьями и Государями, как Ханов, не уступающих в достоинстве Крымскому, и посылал к ним не малочиновных людей, а Бояр для переговоров; грозили в случае отказа местию, напоминая, что отцы их видали Москву, а дети также могут заглянуть в ее стены; хвалились, что у них 300 тысяч воинов и летают как птицы. Бояре обещали им управу и договаривались с ними о свободной торговле, которая обогащала Россию лошадьми и скотом: например, с Ногайскими Послами в 1534 году было 5000 купцов и 50000 лошадей, кроме другого скота. Сверх того сии Князья обязывались извещать Государя о движениях Крымской Орды и не впускать ее разбойников в наши пределы. Шийдяк считал себя главою всех ногаев и писал к Иоанну, чтобы он давал ему, как Хану, урочные поминки. Бояре ответствовали: «Государь жалует и Ханов и Князей, смотря по их услугам, а не дает никому урока». Мамай, именуясь Калгою Шийдяковым, отличался в грамотах своих красноречием и какою-то философиею. Изъявляя Великому Князю сожаление о кончине его родителя, он говорил: «Любезный брат! Не ты и не я произвели смерть, но Адам и Ева. Отцы умирают, дети наследуют их достояние. Плачу с тобою; но покоримся необходимости!» Сии Ногайские грамоты, писанные высокопарным слогом Восточным, показывают некоторое образование ума, замечательное в народе кочующем.

Правительница и Бояре хотели возобновить дружественную связь и с Императором: в 1538 году Послы наши, Юрий Скобельцын и Дмитрий Васильев, ездили к Карлу V и к его брату Фердинанду, Королю Венгерскому и Богемскому.