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