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