Он призвал своих приверженцев в степь подле Голубого озера у подножия Горы-Сердца, где собирался провести традиционный совет племен, который назывался «курултай». Семьи, роды и большие кланы голосовали просто самим своим присутствием. Их присутствие служило официальным признанием Тэмуджина ханом, неявка считалась голосом, отданным против него. Победой стало бы простое собрание кворума. В таком случае был бы составлен список, который бы заучивался наизусть и свидетельствовал о результатах курултая. Тем не менее, никакого такого списка до нас не дошло, что косвенно указывает на весьма скромный результат собрания. Большая часть степных кланов (а возможно, что и большинство их) все еще поддерживали Джамуху.

Племя Тэмуджина, которое состояло теперь из его семьи, нескольких верных друзей и еще нескольких небольших семей, было довольно мало по сравнению с другими племенами степи, а сам он все еще оставался вассалом Он-хана. Чтобы показать, что его попытка добиться титула хана никак не направлена против Он-хана, Тэмуджин послал гонца к предводителю кераитов. Тот должен был уверить Он-хана в том, что единственной целью Тэмуджина было объединение всех разрозненных монгольских племен под властью Он-хана и кераитов. Он-хан легко принял эту весть и, похоже, нимало не беспокоился об объединении монголов, покуда они оставались верны ему. Он-хану было на руку разделение монголов. Подпитывая амбиции обоих юношей, он добивался ослабления влияния обоих и укреплял свою власть над монголами.

Получив поддержку от хана кераитов, которую полагал достаточной, чтобы считаться ханом небольшой группы семей, Тэмуджин начал процесс радикальной перестройки системы управления внутри своего племени. В этом деле он опирался на уроки своей юности. Несколько гэров вождя, которые служили общеплеменным центром или двором предводителя, назывались «орда». В большинстве степных племен ханская «орда» состояла из его родичей и представляла собой своего рода степную аристократию. Нарушая эту неписаную традицию, Тэмуджин назначал на различные ответственные посты людей, ориентируясь на их личные способности и таланты, а не на степень родства с ними. Высшие должности своих личных помощников, нукеров, он отдал двум своим первым приверженцам — Боорчу и Джелме, которые верой и правдой служили ему вот уже десять лет. Тэмуджин-хан отличался удивительной способностью верно оценивать потенциал человека и давать ему именно то задание, с которым он справится с наибольшим успехом.

Он назначил доверенных людей своими поварами (у монголов эта работа заключалась в основном в забое скота, разделке туш и перевозке огромных котлов). Сам Тэмуджин считал их своей первой линией защиты, так как побаивался, что его могут отравить, как и его отца до него. Другие его сторонники стали лучниками, а некоторым было вменено в обязанность стеречь стада, которые зачастую отгонялись на довольно значительное расстояние от основного лагеря. Он назначил своего большого и сильного брата Хасара одним из воинов, отвечавших за защиту лагеря, а своего сводного брата Белгутея поставил присматривать за большим табуном меринов, которых всегда держали поблизости от стойбища, чтобы использовать для верховой езды. Он создал элитный отряд из 150 телохранителей, 70 из которых должны были охранять лагерь днем и 80 — ночью. При Тэмуджине управление нарождающимся племенем монголов стало просто продолжением его личного хозяйства.

Невзирая на успехи Тэмуджина, который добился титула хана и установил новые порядки при своем дворе, Джамуха все еще правил своими сторонниками и отказывался признавать Тэмуджина ханом над всеми монголами. Для Джамухи и аристократических родов «белой кости» Тэмуджин все еще был никем иным, как зарвавшимся выскочкой, которого обожала «черная кость», и которому пришло время преподать хороший урок и поставить его на место. В 1190 году, всего год спустя со времени избрания Тэмуджина ханом, Джамуха использовал убийство одного из его сторонников во время набега приверженцев Тэмуджина как повод для того, чтобы призвать всех своих воинов для мести Тэмуджину. Каждая из сторон собрала армию. С каждой стороны вышло вряд ли более нескольких сотен человек. Впрочем, на этом этапе любые оценки численности войск — не более чем домыслы и теории. В последовавшей битве силы Джамухи обратили воинов Тэмуджина в бегство. Чтобы отбить у них охоту еще когда-либо выступать против него, Джамуха пошел на самые жестокие меры, какие только знали степные войны. Сначала он отрубил голову одному из пленных предводителей и привязал ее к хвосту своего коня. Пролитие крови и осквернение мертвой головы осквернили душу усопшего, а привязывание головы рядом с нечистым местом коня опозорило всю его семью.

Сообщают, что Джамуха приказал сварить заживо семьдесят пленных юношей в котлах. Такая смерть должна была разрушить сами их души и таким образом полностью истребить их. Поскольку у монголов семь считается несчастливым числом, вся история про семьдесят котлов может быть просто поэтическим преувеличением зверств Джамухи, но, тем не менее, «Сокровенное сказание» однозначно указывает на то, что действия упоенного своей победой Джамухи серьезно испортили ему имидж. Такая жестокость с его стороны еще больше усилила антагонизм между старыми аристократическими родами, которые унаследовали власть от предков, и малыми и незначительными семьями, которые могли рассчитывать только на свой талант и личную доблесть. Это происшествие оказалось решающим для Тэмуджина, который проиграл битву, но выиграл поддержку и популярность среди монголов, которые все больше опасались жестокости Джамухи. Воины Тэмуджина были обращены в бегство, но они постепенно вновь собрались под знаменем своего молодого хана.

Его соперничество с Джамухой не получило еще однозначного разрешения, но в 1195 году, когда Тэмуджину исполнилось тридцать три, ему представилась возможность принять участие в набеге, который бы сильно подкрепил его благосостояние и сильно увеличил бы его престиж как воина. Чжурчжени, правившие Китаем, часто вмешивались в степную политику, сея раздоры между племенами, чтобы поддерживать их вечные междоусобные войны и оберегать, таким образом, себя от угрозы со стороны кочевников. Хотя чжурчжени обычно поддерживали татар, они испугались растущего могущества этого племени и подговорили Он-хана собрать армию и совершить набег на татарские земли. Он-хан снова заручился поддержкой Тэмуджина и быстро заключил союз с Золотым Ханом чжурчженей, что позволило им совместно напасть и разграбить селения богатых татар.

Зимой 1196 года владыка кераитов Он-хан и Тэмуджин со своими монгольскими приверженцами выступили в поход против татар. Их набег, организованный в традиционной тактике степных войн, был более масштабным, чем обычно и принес быстрый и легкий успех. Тэмуджин был поражен богатством добычи, которую принес этот набег. Благодаря своей близости к царству чжурчженей и, соответственно, товарам из Китайской империи, у татар было куда больше товаров для торговли, чем у любого другого племени в степи. Среди захваченных богатств «Сокровенное сказание» упоминает окованную серебром колыбель, покрытую шелковым одеялом, украшенным серебряными нитями и жемчугом. Даже захваченные татарские дети были одеты в атласное платье, вышитое золотыми нитями, а один из мальчиков носил золотое кольцо в носу и еще два в ушах. Оборванные монголы никогда не видели такой роскоши.