Тэмучжин щедро вознаградил своих сторонников, деля добычу, доставшуюся от побеждённых керэитов. Двум пастухам, которые предупредили его о неминуемом нападении врага накануне одного из прошлых столкновений, он подарил шатёр ван-хана вместе со всем, что там было ценного. Кроме того, эти пастухи получили высокое звание «колчаноносцев», которое давало им право набирать собственных воинов, оставаться при оружии на пирах и пользоваться личными сосудами для питья. Помимо этого они получали право оставлять себе всю дичь, добытую во время больших сезонных охот. Перспектива получения подобных почестей и льгот привлекала многих на сторону великого хана.
Победа над керэитами усилила мощь монголов и дала Тэмучжину преимущество над другими, более многочисленными кочевыми племенами. Вожди племён из разных районов Центральной и Восточной Монголии являлись к его шатру, чтобы заключить с ним союз и стать его вассалами. Даже бывшие противники выражали свою лояльность. Хан использовал, когда это было возможно, дипломатические приёмы ради обращения своих бывших врагов в новых подданных. Вызывает удивление та решительность, с какой подобные персонажи в результате побед или поражений меняли лагерь и ожесточённо сражались против своих вчерашних союзников. Как и все кочевники, монголы служили не какой-либо идее, нации, стране, а своему господину. Этот принцип господствовал тогда же и в средневековой Европе, где иерархические отношения выстраивались по правилам сюзеренитета и вассалитета. Личные связи и взаимная зависимость наряду с традицией позволяли объединять малые сообщества.
Поражение керэитов предрешило их судьбу. Один род за другим они рассеялись среди других племён, переходя на службу к победителям. Исторические источники не упоминают, однако, о случаях массового истребления или мести по отношению к бывшим подданным Тогорила. Возможно, Тэмучжин в глубине души сохранил память о прежнем боевом содружестве с ван-ханом. Многие керэиты получили у него значительные посты. Но это можно объяснить особыми отношениями, связывавшими Тэмучжина с семьёй Тогорила. Он женился на знатной керэитянке Ибака-Беки, дочери одного из братьев Тогорила. Сын Тэмучжина Тулуй взял в жёны сестру Ибака-Беки Соргактани, которой суждено было стать родоначальницей тюркско-монгольских династий Чингизидов, правивших в Иране и Китае. Их основателями были Мункэ, Хулагу и Хубилай. По-видимому, эта принцесса-несторианка сыграла важную роль в покровительстве миссионерам и в укоренении среди подданных Монгольской империи некоторых христианских понятий. Хубилай-хан, правитель, принимавший у себя Марко Поло, покровительствовал несторианам и даже учредил службу, которая поддерживала это верование. Он известен в основном благожелательным отношением к идеям, приходившим с христианского Запада.
Зимой 1203 года Тэмучжин обосновался в Центральной Монголии, в районе под названием Верблюжья степь (Темейен-кээр). Там он узнал от осведомителей, что Тогорил с сыном по-прежнему укрывается у найманов. В поисках убежища беглецы добирались до них через негостеприимные степи в сопровождении нескольких верных людей, как и они, лишённых всего и перебивавшихся случайными набегами или охотой. И однажды Тогорил был захвачен людьми из одного шатра найманов. Их вождь, полагавший, что имеет дело с обыкновенным скотокрадом, убил старика без лишних разбирательств. Вероятно, Тогорил перед смертью сообщил, кто он такой, поскольку вскоре по степи разошёлся слух, что какой-то простой хозяин стойбища убил самого ван-хана керэитов. Новость эта дошла до главы найманов, который приказал разыскать тело Тогорила. Человек, который нашёл его, отрубил голову и привёз её главе найманов Таян-хану. Тот, сожалея, что не смог встретить побеждённого властителя керэитов, или испытывая угрызения совести из-за того, что не смог уберечь его от такого позорного конца, устроил в честь усопшего Тогорила траурную церемонию. Он поместил его голову в серебряный ларец, а ларец поставил на подушку из белого войлока. Потом принцесса Гурбесу велела принести кубки для возлияний, музыканты заиграли грустные мелодии. Но легенда гласит: когда сосуд с напитком поднесли к голове Тогорила, его мёртвые губы начали улыбаться и даже ухмыляться. Суеверный Таян-хан опрокинул ларец наземь и растоптал его сапогом. Придя в ужас от такого святотатства, один из сподвижников Таян-хана объявил своему господину, что его власти грозит неминуемая беда.
Наследник несчастного Тогорила нашёл убежище в какой-то пустынной местности, где жил как отверженный. Оставленный последними сторонниками, преданный собственным оруженосцем, он достиг границ государства Си Ся к югу от Монголии, близ современной китайской провинции Ганьсу. Без союзников и без каких-либо средств он промышлял грабежом до тех пор, пока однажды в оазисе Куча на уйгурской территории жители деревни не убили его в какой-то стычке.
Тэмучжин не замедлил подчинить себе племена, которые раньше были союзниками Тогорила. К концу 1203 года он объединил под своей властью десятки тысяч кочевников Центральной и Восточной Монголии. Но на западе страны кочевники ещё оставались независимыми.
Племя найманов занимало обширное степное пространство по обе стороны Алтайских гор и бассейн верхнего течения Иртыша. Вождь найманов, хотя и был, по-видимому, человеком довольно посредственным, всё же не мог не догадываться о далекоидущих замыслах Тэмучжина. Найманы были тюркским этносом, находившимся в стадии глубокой трансформации, «перехода от тюркофонии к монголофонии», по замечанию Жана Поля Ру. Они находились под влиянием как несторианцев-уйгуров, так и шаманизма. Несомненно, правящая верхушка найманов уже вышла из того «примитивного» состояния, в котором пока ещё находилась монгольская знать. Свидетельством тому может служить высокомерное рассуждение принцессы Гурбесу, которая якобы называла своих соседей «вонючими монголами», добавляя при этом, что даже самые воспитанные монгольские принцессы не знали, что такое мыть руки и ноги. Лоск культуры найманов был результатом более развитого ремесла, более тесных связей с осёдлыми народами и контактами с западными путешественниками. Рубрук говорит о найманах-несторианах как о настоящих подданных Жана Проповедника.
Чтобы подготовиться к набегу монголов, Таян-хан решил для начала напасть на них с юга. Он вступил в контакт с онгутами, тюркским народом, также несторианского вероисповедания, но говорившим на одном из монгольских диалектов. Они кочевали в районе к северу от Великой стены вблизи Сюнаня. Но онгуты отказались от союза с Таян-ханом и предупредили о его намерениях Тэмучжина.
Тот узнал о военных приготовлениях найманов во время охоты в степи Ослиная Спина. Начиналось лето, цветущие тюльпаны, нарциссы, ирисы ковром покрывали степные дали. Эдельвейсы и тимьян захватывали пространства, которым вскоре предстояло перейти во власть осенних холодов. Там Тэмучжин собрал верных ему людей. По-видимому, хан посчитал, что лошади его ещё недостаточно откормились, и решил отложить выступление. Но его брат Тэмуге и сводный брат Бэлгутэй горели нетерпением, желая сразиться с противником, и партия войны взяла верх. Но всё же Тэмучжин охладил пыл своих военачальников и начал тщательную подготовку к наступлению на найманов. Ему предстояло мобилизовать союзные племена и выработать стратегию.
Как всегда перед боевыми действиями, шаманы принесли ритуальную жертву перед туком — куском ткани, украшенным девятью чёрными конскими хвостами, который несли впереди войска. Перед этим знаменем, в котором жил сульде, родовой дух-покровитель, они лили из чаш кумыс. Знаки судьбы, истолкованные шаманами, были, разумеется, благоприятными для Тэмучжина, и тот сразу же направил свои войска на запад, по течению Керулена. Долгий и трудный переход через каменистые склоны холмов и речки привёл их к месту сражения. Битва при Хангае была жестокой. Она обескровила войско найманов и положила конец их могуществу.