В 1419 году золотоордынский трон перешел от детей Тохтамыша к потомку Тука-Тимура, Улуг-Махмеду (Большой Махмед, возможно, в смысле – Старший Махмед). Фактически его власть признала только западная часть Золотой Орды. Регион нижней Волги контролировал сын Тохтамыша Кепек (Kib"ak). Да и в западной части кипчакских степей власть Улуг-Махмеда была непрочной; некоторые татарские князья отказывались ему подчиняться. В этих обстоятельствах понятно, что Улуг-Махмед обратился за помощью к великому князю Литвы. Витовт, таким образом, получил возможность продолжить свою политику вмешательства в дела Золотой Орды через дружественных ему ханов. Теперь он стал самым могущественным правителем Восточной Европы, а Великое княжество Литовское превратилось в важнейший фактор восточноевропейской политики. Влияние Витовта чувствовалось даже в центральноевропейских делах, главным в которых тогда было движение гуситов в Богемии. И гуситы, и император Сигизмунд пытались привлечь Витовта на свою сторону. В 1421 году посетившая Витовта чешская делегация предложила ему корону Богемии. Он, в принципе, согласился и послал в Богемию своего родственника Сигизмунда Корибутовича (сына Корибуты, внука Ольгерда) с 5 000 подразделением литовско-русских войск879
. Позже между гуситскими лидерами и Витовтом возникли разногласия, преимущественно из-за возражений короля Польши по поводу сотрудничества Литвы с Богемией. Под давлением Ягайло Витовт разорвал отношения с чехами, и Сигизмунд Корибутович из Богемии ушел. Весь план объединения Богемии с Литвой и Западной Русью, таким образом, провалился.В Золотой Орде неустойчивое равновесие между местными ханами в 1422 году нарушило вторжение в регион нижней Волги хана Барака (внука Урус-хана) из Казахстана. За два года узбеки Барака разбили и Махмеда, и его соперника Кепека. Попытка двоюродного брата Улуг-Махмеда, Давлет-Берди, противостоять захватчику тоже ни к чему не привела. Все три побежденных хана вынуждены были уходить на запад. Кепек совершил набег на русские города Рязань и Одоев (1422 год), но не смог там закрепиться. Улуг-Махмед отправился в Литву просить Витовта о помощи. Давлет-Берди, воспользовавшись общим замешательством, захватил Крым (примерно 1425 год)880
.Тем временем Барак, посеяв всю эту смуту, вернулся в Казахстан, отягощенный добычей (1425). Теперь он достаточно окреп, чтобы объявить себя независимым ханом – ханом узбеков. Внук Тамерлана Улуг-Бек, который правил в Самарканде и считал Барака своим вассалом, возмутился этим и два года спустя лично повел армию в Казахстан, чтобы вновь его завоевать. Барак победил Улуг-Бека (1427 год)881
. Вскоре, однако, узбекские эмиры организовали против Барака заговор и сместили его (1428). Следующий избранный хан – Абуль-Хаир, потомок Шибана – правил с 1428 по 1468 год, сумел консолидировать узбекское государство и дал начало династии Шибанидов.Что же касается положения в Крыму, то в 1426 году Давлет-Берди, стараясь укрепить свой контроль над Крымом, направил письмо султану Египта, информируя его о волнениях среди кипчаков и предлагая военный союз. Улуг-Махмед, однако, скоро вытеснил Давлет-Берди из Крыма и, с помощью местной татарской семьи Ширинов, создал там собственную ставку (1427 год). После этого имя Давлет-Берди из истории исчезло. Известно, однако, что примерно в 1428 году в Литву прибыл и обратился к Витовту за поддержкой хан Хаджи-Гирей. В.Д. Смирнов выдвигает вполне правдоподобное предположение, что один хан мог иметь два имени, и был известен сначала под одним, а потом под другим882
.Политический триумф Улуг-Махмеда омрачился эпидемией чумы, начавшейся на Западе, но не на Востоке. На Руси она сначала распространилась в Новгороде, затем проникла в Москву и, наконец, в половецкие степи. Первым дипломатическим шагом Улуг-Махмеда было установить дружественные отношения с оттоманским султаном Мурадом II883
. Через год хан отправил в Каир посла провести переговоры о союзе с мамлюками. Тогда как свидетельств о том, что какая-либо из сторон извлекла выгоду из этих переговоров, нет, то прибытие кораблей из Крыма в то время, когда в половецких степях свирепствовала чума, оказалось для Египта несчастьем, поскольку принесло туда болезнь884.