Из Бухары Чингисхан проследовал в Самарканд, где к нему присоединились Чагатай и Угэдэй, которые взяли Утрар и покарали вероломного правителя города, залив ему в глотку расплавленное золото. Пленных, взятых в Бухаре, гнали перед воинами в боевом порядке, чтобы создать впечатление большой армии. Через пять дней (март 1220 года) Самарканд капитулировал. Жителям приказали покинуть город, который легче было грабить в их отсутствие. Тюркский гарнизон был умерщвлен, а ремесленники и мастеровые числом более 30 тысяч человек уведены в Монголию. Священнослужителей пощадили. Но убийств было много, и, когда горожанам позволили вернуться, только четвертая часть жилищ была заселена. Перепуганный разрушительной лавиной, обрушившейся на его государство, султан Мухаммед бежал на запад в надежде собрать новую армию в персидском Ираке, несмотря на попытки его отважного сына Джелал ад-Дина переубедить отца. Юноша утверждал, что такое поведение будет трусливым дезертирством в глазах страдающего народа. Чингисхан приказал своим командирам Джэбэ и Субэдэю гнать несчастного суверена из города в город, из провинции в провинцию. Монгольская кавалерия преследовала его в Тусе (где Субэдэй сжег гробницу Гарун ар-Рашида), Рее и Хамадане, где контакт был потерян. Беглец сумел добраться до каспийского побережья в Абаскуме, возле которого находится небольшой островок, на котором он в декабре 1220 года нашел убежище и смерть. Преследователи, несомненно, были вдохновлены успешным продвижением по деморализованному и почти беззащитному государству. Если верить персидскому историку XV века Мирхонду, монголам существенно помог раскол внутри ислама. Историк предполагает, что их попросили суннитские мусульмане очистить от еретиков-шиитов город Кум, который находился у них на пути. Монголы продолжали рваться вперед. Они совершили то, чему не было прецедента раньше и что практически никому не удалось повторить впоследствии. Направляясь на север в Азербайджан, богатые пастбища которого всегда привлекали кочевников, они ворвались в христианское грузинское царство, армия которого была разгромлена в феврале 1221 года у Тифлиса. И первая новость о монголах достигла Западной Европы в 1224 году в письме царицы Грузии Русудан папе Гонорию IV. Монголы разрушили город Марата, древнюю столицу Азербайджана. Этот город находился на плодородных, хорошо орошаемых склонах, в нескольких милях от Тебриза. Монголы, как это уже вошло у них в привычку, заставили пленных идти перед армией и, захватив город, убили население. Через некоторое время они вернулись и добили тех людей, которые успели спрятаться и после ухода врага выбрались из укрытий.
После этого они подавили восстание в Хамадане, полностью уничтожив город и всех его жителей. Далее их путь лежал к перевалам Дербента. Этот город средневековые арабы и персы называли Баб-аль-Абваб, Вата врат. Врата – это перевалы через Кавказ у западной оконечности Каспия. Дербент был городом, крепостью, гаванью и горным проходом. Пройдя через перевалы, они вышли к степям, расположенным к северу от Кавказа, где их встретила коалиция из аланов, черкесов и кипчаков, желавших преградить им путь на русские равнины. Аланы – древний иранский народ, живший на Северном Кавказе. В X веке они были обращены в христианство византийскими миссионерами и во время монгольского нашествия принадлежали к православной церкви. Черкесы – иберо-кавказский народ, живший на Кубани. Во время монгольского нашествия они тоже были христианами. Кипчаки, они же куманы и половцы, – племенная конфедерация, долгое время обитавшая в степях Северного Причерноморья. Они были кочевниками, неграмотными и нецивилизованными. Умело использовав разговоры о тюркско-монгольской солидарности, они отделили кипчаков от союза, который затем легко разбили. Русские князья, которые трудолюбиво собрали плохо организованную разношерстную армию, были разбиты в мае 1223 года в сражении на реке Калка, небольшой речушке, впадающей в Азовское море. Разграбив Судак, генуэзскую торговую колонию в Крыму, монголы двинулись вверх по Волге на волжских булгар и тюрок-канглы. Обойдя северные берега Каспия, они соединились с главными силами армии Чингисхана в степях за Яксартом. Этот потрясающий рейд, в процессе которого было разгромлено двадцать народов и совершен полный оборот вокруг Каспия, не имел непосредственных политических последствий, но создал прецедент для вторжения в Восточную Европу двадцатью годами позже.
Тем временем Чингисхан продолжал методично разрушать Хорезмийское государство. Прежде чем двинуться к югу от Оксуса в Хорасан, он решил покорить колыбель шахов, плодородный регион к югу от Аральского моря, центром обороны которого был город-крепость Гургандж. Географ Якут в 1219 году утверждал, что никогда не видел более могучего и красивого города. Годом позже он был полностью разрушен, правда, возможно, не так монголами, как наводнениями, вызванными разрушениями плотин.