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