За мелкую служебную провинность его приговорили к смертной казни. Мугулюй бежал и укрылся в степях, к нему присоединились другие дезертиры и беглецы — человек 100–200. По-видимому, он обладал качествами вожака и недюжинной физической силой. Отряд, сложившийся вокруг Мугулюя, подчинялся ему беспрекословно. Они присоединились к кочевому племени — и вскоре Мугулюй возглавил его. Это небольшое сообщество кочевников стало ядром будущего жужаньского каганата. Их основным занятием был выпас овец и грабительские набеги на пастбища соседних племенных союзов.
После смерти Мугулюя вождём кочевья стал его сын Цзюйлухуэй. В китайских источниках его относили к племени дунху. Именно в его времена племя приняло название жоужань или жужань, что в переводе, предположительно, означает «ставка вождя». Впрочем, есть и иные трактовки данного слова: с монгольского языка его можно перевести как «порядок», «миролюбие», «согласие».
Китайцы презрительно называли из «жуаньуань» — то есть, пресмыкающиеся, насекомые, варвары. Они считали жужаней не народов, не племенем, а разросшейся бандой разбойников.
Орда, собравшаяся вокруг династии вождей, была разноплеменной, но придворный историк китайской династии Северная Вэй сообщает, что господствующее среди жужаней племя было потомками сяньби — древнемонгольских орд, кочевавших по территории нынешней Внутренней Монголии. Вэйцы сами были недавними кочевниками — и неплохо разбирались в особенностях степных цивилизаций.
По-настоящему крупным и мощным кочевое образование жужаней стало в конце IV века, когда его вождем — шаньюем — стал Юйцзюлюй Шэлунь. Он пришел к власти после кровопролитной междоусобицы, уничтожив семейство своего предшественника. Первым успехом молодого и яростного вожака стала война с вэйской армией, от которой кочевникам под его командованием удалось отбиться.
Шэлунь провёл реформу войска на основе жестокой дисциплины: отказался от родовой системы, присущей древним монголам. Отныне 100 воинов составляли знамя, десять знамён составляли полк. Начальников выбирали простые воины, храбрецы получали больше добычи, трусов и дезертиров закидывали камнями и забивали палками. Конница Шелуня сметала всё на своём пути, стремясь к новой добыче, к преумножению числа невольников.
В результате ему удалось укрепить жужаньскую орду. Они покорили все мелкие кочевые племена на севере нынешней Монголии, увеличив тем самым свое войско. Шэлунь заключил союз с империей Цинь, а свою ставку устроил на реке Жоло.
Не всегда ему сопутствовали победы. Хуннское племя князя Жибаецзи разбило жужаней при реке Егэнь. Но после поражения Шэлунь собрался с силами и вскоре покорил это племя.
В 402 году Шэлунь провозгласил себя ханом ханов, то есть каганом под именем Цюдоуфа Хан. Он первым провозгласил этот титул, который кочевники считали равным императорскому.
После этого жужани активно вмешивались в войны, которые вели между собой китайские монархии — Северная Вэй и Цинь. Жужани поддерживали последних и с переменным успехом постоянно совершали набеги на вэйские земли. Государство первого кагана простиралось от Кореи до Карашара в Восточном Притяньшанье, от Гоби до верховий Амура. Жужани стали гегемонами Великой степи. Территория, подвластная каганату, делилась на два крыла, во главе которых стояли вожди, назначавшие в своих владениях тысячников, сотников, десятников.
Шэлунь и умер во время войны против вэйцев. Каганом стал его брат Хулюй, продолживший тактику набегов и шантажа соседей.
Он начал с покорения енисейских киргизов, закрепился на кочевьях на севере Монголии. К покоренным кочевникам жужани относились без снисхождения. Подчиненные племена подвергались жестокой эксплуатации и облагались данью. Чтобы закабалить молодых воинов из покоренных племен, жужани применяли изощренные пытки. Они надевали на голову жертвы тяжелую и плотную верблюжью шкуру, так называемую шири. После этого пленников заковывали в деревянную шейную колоду, которая не позволяла дотянуться головой до земли, и связывали руки и ноги. В этом виде их отвозили подальше от поселений и бросали на несколько суток на солнцепеке. Выживали один или двое из 5–6 человек. Погибали не от голода жажды, а от невыносимых страданий, которые причиняла усыхающая, сжимавшаяся на голове верблюжья кожей. В результате воин лишался памяти о своем племени и превращался в покорное существо. Таким рабам — манкуртам — поручали самую тяжкую работу. Им достаточно было получать скромную пищу — и они работали за троих. А жужани хорошо понимали, что стереть память — значит, полностью подчинить человека.
Но их гнет был чрезмерно жесток и требовал постоянных карательных экспедиций против непокорных. Неудивительно, что во владениях кагана нередко возникали очаги сопротивления. Самыми неуступчивыми из покоренных племен были уйгуры.
Чтобы защитить себя от постоянных нападений жужаней, вэйцы к 423 году удлинили Великую стену на тысячу километров! Китайские авторы пишут, что в это время у жужаней было до миллиона лошадей и бесчисленное количество овец.