蠕蠕族，是東胡族的後代子孫，姓郁久閭氏。傳說在神元帝末年，有人在東胡搶劫馬匹時抓到一個奴隸，頭髮只齊眉毛那麼長，不知道自己的姓名，主人就給他取名叫木骨閭。「木骨閭」就是頭禿的意思。木骨閭與郁久閭聲音相近，所以他的子孫就以郁久閭作為姓氏。木骨閭成年後，被免去奴隸身份而充當騎卒。穆帝時，他因為行軍誤期而犯了斬首之罪，就逃到沙漠上的奚谷谷之間藏匿起來，聚合逃亡者共一百餘人，依附於紇突鄰部。木骨閭死後，其子車鹿會十分雄偉強健，開始形成自己的部族，自號為柔然，而役屬於中國。後來世祖因為這個部族愚昧無知，就像是蟲子，所以把它的稱號改為蠕蠕。
車鹿會當了部族首領之後，每年都向朝廷進貢馬匹牲畜和貂豸內皮，他們冬天就遷徙到大沙漠以南，夏天又遷回大沙漠之北。車鹿會死後，其子吐奴傀繼位。吐奴傀死後，其子跋提繼位。跋提死後，其子地粟袁繼位。地粟袁死後，部族就一分為二，地粟袁的長子匹候跋繼承父位居於東邊，次子..紇提另居西邊。到昭成帝駕崩，..紇提依附於衛辰而背叛我朝。登國年間大魏出兵討伐他，蠕蠕部族便遷移逃跑，將其追逐到大沙漠南床山下，把它打敗，俘虜了其部族人的一半。匹候跋和部帥屋擊各自收集其餘部逃走，我朝派長孫嵩和長孫肥繼續追擊，穿過大沙漠。長孫嵩追到平望川，大破屋擊，並將他擒獲，斬首示眾。長孫肥追至諑邪山，逼近匹候跋，匹候跋所部全部投降。又抓獲..紇提之子曷多汗和曷多汗之兄詰歸之、社侖、斛律等人及其宗族黨羽數百人，把他們分配到各部。..紇提向西而逃，企圖回到衛辰那裡去，太祖下令追擊，到達跋那山，..紇提也被迫投降，太祖對他像往日那樣加以撫慰。
登國九年(394)，曷多汗與社侖率部眾背棄其父..紇提向西逃走，長孫肥率輕騎追趕，追至上郡跋那山，斬曷多汗，並將跟隨他叛逃的人全都殺死。社侖帶領數百人逃奔匹候跋，匹候跋把他安置在南部邊邑，離自己的王庭五百里，並令自己的四個兒子對他進行監視。不久，社侖率領他的親隨捉拿匹候跋的四個兒子而反叛，襲擊匹候跋。匹候跋的其他幾個兒子收集餘部，逃走依附於高車的斛律部族。社侖凶狠狡詐而有權變，過了一個多月，就釋放了匹候跋，送還了他的幾個兒子，企圖將他們聚而殲之。於是暗中發兵襲擊匹候跋，將他殺死。匹候跋之子啟拔、吳頡等十五人歸附於太祖。社侖殺了匹候跋之後，害怕魏軍前來征討，就搶掠五原以西的各個部落，向北穿過大沙漠。太祖授予啟拔、吳頡以安遠將軍、平棘侯之職。社侖與後秦結和親之約。太祖派材官將軍和突襲擊黜弗、素古延各部族，社侖派騎兵援救素古延，和突回兵攻擊，大敗社侖。
社侖遠逃到大沙漠以北，侵犯高車族，深入高車境內，於是兼併鄰近的各個部族，其凶頑之勢日益加劇。社侖又遷移到北邊的弱洛水，開始建立軍法：一千人為軍，每軍設置一個將，一百人為幢，每幢設置一個帥；作戰時搶在前面的人就賜給虜獲的俘虜和財物，膽小退卻的人就用石頭擊破腦袋而死，或者暫時用棍子、鞭子痛打。因其沒有文字來記載，將帥就用羊屎來粗略地計算兵員數目，後來才稍為懂得用刻木的方法來記事。社侖部的西北邊有匈奴余族，其部落非常富足強盛，部落頭領名叫拔也稽，他發兵攻擊社侖，社侖在安頁根河迎戰，大破拔也稽軍，後來其部族全都被社侖所兼併。於是其政權一時十分強盛。部族人隨水草之地遊牧，其西邊是焉耆國的疆土，東邊是朝鮮國的疆土，北邊穿過大沙漠，直到沙漠盡頭，南邊則臨大沙漠。其經常聚會議事的中心在敦煌、張掖的北部。鄰近的小柄都深受其侵犯擄掠之害，只得同它聯絡關係而依附於它，於是社侖自號為丘豆伐可汗。「丘豆伐」相當於北魏人所說的「駕馭開張」的意思，「可汗」相當於北魏所說的皇帝。蠕蠕國的風俗，國君和大臣憑他的行為能力給予稱號，就像中國的為某人立謚號，人死之後，不再追加稱號。太祖對尚書崔玄伯說道：「蠕蠕族的人，歷來號稱凶頑愚蠢，每次外出搶掠，都要駕著母牛奔逃，驅趕著犍牛跟隨著跑，母牛往往趴伏著不能往前跑。別的部族的人教給他們用犍牛替換母牛，蠕蠕人說『它的母親都不能走，何況它的兒子呢』，終究不予以替換，於是只能被敵方俘虜。現在社侖學習中國，建立軍法，設置作戰的陣式，終於成為邊地的禍害。道家曾說聖人生，大盜起，確實說得不錯啊。」
天興五年(402)，社侖聽說太祖征討姚興，就來侵犯邊塞，進入參合陂，南邊到達豺山和善無北澤。當時太祖派常山王拓跋遵率一萬騎兵追擊，沒有追上。天賜年間，社侖的堂弟悅代、大那等人圖謀殺死社侖而擁立大那，被社侖發覺，大那等人前來投奔，朝廷授予大那冠軍將軍、西平侯，悅代為越騎校尉、易陽子。天賜三年(406)夏，社侖侵犯邊境，永興元年(409)冬，又來侵犯邊塞。永興二年(410)，太宗發兵討伐，社侖逃走，死於途中。社侖的兒子度拔年幼，不能控制其部眾，部落就擁立社侖之弟斛律為首領，號為藹苦蓋可汗，「藹苦蓋」就是魏人所說「姿質美好」的意思。
斛律於北邊兼併了賀術也骨國，東邊攻破譬歷辰部落。永興三年(411)，斛律的同宗人悅侯咄角氐乾等數百人前來投降。斛律懼怕朝廷威嚴而只顧防守，不敢南來侵犯，於是北部邊境得以安寧。神瑞元年(414)，斛律與馮跋聯姻和親，馮跋娶斛律的女兒為妻，將要舉行婚禮。斛律長兄之子步鹿真對斛律說：「你的女兒年尚幼小，遠嫁到外地，恐怕會因想家而憂思得病，可以派大臣樹黎、勿地延等的女兒作為陪嫁。」斛律不答應。步鹿真出來後對樹黎等人說：「斛律想要把你們的女兒作為陪嫁，遠送到別的國家。」於是樹黎就與步鹿真共同策劃，派一批勇士趁夜晚靠近斛律所住的氈帳，等到他出來時就把他扣押起來，並讓他陪他的女兒嫁到和龍城。於是就立步鹿真為首領。
步鹿真即位後，把政事委付給了樹黎。當初，高車族的叱洛侯背叛他的首領，引導社侖攻破各個部落，社侖十分感激他，讓他做了大人。有一次，步鹿真同社侖的兒子社拔一道到叱洛侯家中，與他年輕的妻子私通。他的妻子告訴步鹿真說，叱洛侯想要推舉大檀為首領，送給大檀一副黃金製的馬勒作為信物。步鹿真聽了後，回去派了八千名騎兵包圍了叱洛侯，叱洛侯被迫燒燬了他的所有珍寶，自刎而死。於是步鹿真就乘其不備襲擊大檀，大檀發兵捉拿了步鹿真和社拔，把他們絞死，就自己立為部族首領。
大檀，是社侖的叔父僕渾之子，先前統率其他部落，鎮守在西部邊界，由於他很得人心，部族的人都推崇擁戴他，自號為牟汗紇升蓋可汗，就是魏國人所說「制勝」的意思。斛律父子到了和龍城以後，馮跋封他為上谷侯。後來大檀率部向南遷移進犯邊塞，太宗親自帶兵征討，大檀畏懼逃跑。太宗派山陽侯奚斤等人領兵追擊，碰上嚴寒大雪，戰士們凍死的、凍掉手指的佔十分之二三。到太宗駕崩後，世祖即位，大檀聽到這消息大喜，始光元年(424)秋，就來侵犯雲中郡。世祖帶兵親往討伐，三天兩夜趕赴雲中。大檀率領騎兵包圍世祖，共圍了五十層，後面的馬頭緊靠前面的馬，一層接一層就像是土牆一樣。魏軍士卒十分恐慌，而世祖卻神色自若，於是軍情才得以安定。早先，大檀的弟弟大那與社侖爭奪領導權，失敗後投奔朝廷。大檀以大那的兒子於陟斤為部帥，魏朝軍士用亂箭將於陟斤射死，大檀恐懼，就退了回去。始光二年(425)，世祖發兵大舉征伐，分兵從東西五路齊發並進：平陽王長孫翰等人從黑漠進發，汝陰公長孫道生從黑白兩漠之間進軍，世祖從中路前進，東平公娥清從偏西方向經栗園進軍，宜城王奚斤、將軍安原等從西路經爾寒山進軍。各部分頭前進到達漠南，留下輜重，騎兵輕裝只帶十五天的乾糧，橫穿大沙漠合兵圍剿，大檀部落驚恐懼怕，向北而逃。神..元年(428)八月，大檀又派兒子率騎兵萬餘人侵入邊塞，殺戮搶掠邊地居民而逃。魏朝附屬國高車出兵追擊，將他們打敗。皇帝從廣寧回朝，派兵追擊卻沒有追到。
神..二年(429)四月，世祖在南郊操練兵馬，準備攻擊大檀。朝廷的公卿大臣們都不願意出兵，術士張淵、徐辯用觀察星象的結果去勸阻世祖，世祖卻聽從崔浩的建議決定進兵。剛好派往江南的使者回來，報告了劉義隆想要進犯黃河以南地區的情況，劉義隆對使者說：「你速速回去告知魏朝皇帝，歸還我黃河以南地區，我就立即罷兵，不然的話，我就會下令將士全力進攻。」世祖聽說後大笑，對朝廷公卿大臣說：「劉義隆不過是一個龜鱉小兒，連自救都顧不上，能有什麼作為。即使他敢於來犯，倘若不先滅除蠕蠕，就等於是坐等賊寇到來，使我們腹背受敵，這不是上策。我出兵征討蠕蠕的主意已經定了。」於是，皇帝的車駕出東路向黑山進發，平陽王長孫翰率兵從西路向大娥山進發，兩路合兵直逼蠕蠕的政權中心。同年五月，軍隊駐紮在大沙漠之南，留下輜重輕裝奔襲，兵到栗水，大檀所部聞風向西逃竄。大檀的弟弟匹黎原先掌管東邊部落，打算趕赴大檀所在之處，途中遭遇長孫翰的軍隊，長孫翰派騎兵進擊，殺死其酋長數百人。大檀聞訊十分震驚恐懼，就率領他的部族，燒掉氈帳房舍，向西逃走，不留行跡，沒有人知道他們逃到了哪裡。於是，蠕蠕國部落四處奔散，竄逃藏匿於山谷地區，棄下各種牲畜遍佈四野，沒有人看管照料。世祖沿著栗水向西而行，路經漢代大將竇憲昔日的營壘。六月，世祖的車駕駐紮在兔園水，這裡離平城有三千七百里。分兵搜索征討，東邊到達大沙漠，西邊接近張掖水，北邊越過燕然山，東西五千餘里，南北三千里。高車各部族捕殺大檀屬下的人，前後有三十餘萬人歸降，俘獲大小頭領及胡馬百餘萬匹。這年八月，世祖聽說東部的高車人屯紮在已尼陂，人口和牲畜非常多，離官軍一千多里。於是派左僕射安原等人前往征伐。軍隊開到已尼陂，高車各部落紛紛向官軍投降，共計數十萬人。
大檀的部落從此衰弱不堪，大檀也發病而死，其子吳提繼位，號敕連可汗，是魏人所說「神聖」之意。神鹿加四年(431)，吳提派使者向朝廷進貢。起先，北方邊境魏軍的哨騎抓獲吳提派往南邊巡邏的士卒二十餘人，世祖賜給他們衣服，把他們遣送回去。吳提上下的人都感激朝廷恩德，所以就向朝廷納貢。世祖將其使者當作貴賓給以厚待，並送他們回去。延和三年(434)二月，因吳提娶了西海公主為妻，世祖又派使者前往把吳提的妹妹納為夫人，後又將她進升為左昭儀。吳提派其兄禿鹿傀和近侍數百人前來朝貢，獻馬二千匹，世祖大悅，對他們頒賜甚為豐厚。到了太延二年(436)，吳提又斷絕和睦關係進犯邊塞。四年(438)，世祖帶兵到達五原，征伐吳提。樂平王拓跋丕、河東公賀多羅督率十五員大將出兵東路，永昌王拓跋健、宜都王穆壽督率十五員大將從西路進軍，世祖從中路進發。到達浚稽山，又將中路軍分成兩路，陳留王拓跋崇由大澤向涿邪山前進，世祖則從浚稽往北向天山進軍。軍隊登上西邊的白阜山，在石頭上刻字記載其行蹤，終因沒有發現蠕蠕人的蹤跡而回還。當時漠北大旱，大沙漠中沒有水草，軍馬死亡甚多。太延五年(439)，世祖向西討伐沮渠牧犍，宜都王穆壽輔助景穆帝留守京師，長樂王嵇敬、建寧王拓跋崇率二萬人鎮守漠南，以防備蠕蠕來犯。吳提果然侵犯邊塞，穆壽一向不加防備，致使敵軍進至七介山，京城的人大為驚恐，爭相奔往中城。司空長孫道生領兵迎敵於吐頹山。吳提前來侵犯之時，留其兄乞列歸與北邊各鎮的軍隊對峙，長樂王嵇敬、建寧王拓跋崇等人率兵大破乞列歸於陰山北面，將他擒獲。乞列歸歎道：「這是沮渠牧犍陷我於死地啊。」又抓獲乞列歸的伯父他吾無鹿胡及其將帥五百人，斬首萬餘級。吳提聞訊逃走，長孫道生隨後追擊，追到漠南而還。真君四年(443)，世祖駕幸漠南，分兵四路：樂安王拓跋范、建寧王拓跋崇各領十五員大將出東路，樂平王拓跋丕督率十五員大將出西路，世祖率軍出中路，中山王拓跋辰統領十五員大將為中路軍的後繼。世祖到達鹿渾谷，將要同敵軍遭遇，吳提逃走，魏軍追至安頁根河，將吳提軍擊破。世祖到達石水而還。真君五年(444)，世祖又到漠南，想要攻擊吳提，吳提逃到很遠的地方，世祖才回朝。
吳提死後，其子吐賀真繼位，號處可汗，是魏人所說「答應」的意思。真君十年(449)正月，世祖北伐，高涼王拓跋那出東路，略陽王拓跋羯兒出西路，世祖與景穆帝由中路出涿邪山。吐賀真的部落首領爾綿他拔等人率一千多家前來投降。當時，魏軍前行數千里，吐賀真由於剛剛即位，十分畏懼就遠遠地逃遁。這一年九月，世祖又一次北伐，高涼王拓跋那從東路進發，略陽王拓跋羯兒從中路出兵，與各路軍約定時間在地弗池會師。吐賀真集合全國的精銳兵力，軍隊物資非常充足，將高涼王拓跋那圍困數十層，高涼王拓跋那挖掘長長的圍子堅守，雙方相持好幾天。吐賀真多次向拓跋那挑戰，都沒有成功，因為高涼王拓跋那兵少而防守堅固，吐賀真懷疑魏軍大部隊很快就會到來，就解除包圍連夜逃走。高涼王拓跋那領軍追擊，一連追了九天九夜，吐賀真越發畏懼，就丟棄輜重，跨越穹隆嶺逃之夭夭。高涼王拓跋那收集敵軍的輜重，領軍而還，與世祖會師於廣澤。略陽王拓跋羯兒收聚蠕蠕族的人口畜產達百餘萬。從此以後，吐賀真力量日益薄弱，逃往遠處，於是邊疆的敵患得以停息。太安四年(458)，高宗北征，出動騎兵十萬，戰車十五萬輛，旌旗相連長達千里，穿越大沙漠。吐賀真逃往遠地，其屬下烏朱駕頹率數千部落前來投降，於是高宗令人在石頭上刊刻記載北征之功，回到京城。高宗承世祖對蠕蠕進行征伐之後，有意要休養生息，蠕蠕族也畏懼朝廷威勢而遠竄北方，再也不敢南犯。
和平五年(464)，吐賀真死，其子予成繼位，號受羅部真可汗，這是魏人所說「恩惠」的意思。予成自定年號為永康元年，率領其部族又來侵犯邊境，魏朝北方各鎮流動出擊的軍隊把他們打敗。皇興四年(470)，予成又來犯邊，顯祖帶兵北伐。京兆王子推、東陽公元丕督率諸軍出西路，任城王元雲等督率軍隊出東路，汝陰王元賜、濟南公羅烏拔督率軍隊為前鋒，隴西王源賀督率諸軍為後繼。各路將領與顯祖在女水之濱會合，顯祖親臨誓師，詔令諸將說：「打仗用兵不在於多而在於出奇制勝，你們要為朝廷奮力作戰，作戰方略朕已成竹在胸。」於是就挑選精兵五千人向敵軍挑戰，佈置許多奇兵來迷惑對方。蠕蠕軍潰敗逃竄，魏軍向北追逐三十餘里，斬首五萬級，敵軍投降的有萬餘人，繳獲軍馬兵器不計其數。十九天之內，往返行軍六千餘里，把女水改名為武川，並撰寫《北征頌》，刊刻在大石上以記載戰功。
延興五年(475)，予成向朝廷請求通婚，朝中官吏認為予成屢次侵犯邊塞，請求皇帝拒絕他派來的使者，發兵討伐予成。顯祖說：「蠕蠕人好像禽獸，貪婪而不講信義，朕應當以信用和誠懇對待他們，不能強行與之斷絕。予成既然懂得悔過，派使者前來請和，要求結姻攀附，怎麼能辜負他的一片誠意？」於是下詔回復說：「所論通婚之事，說明你開始有所轉變，但探究事情的道理，卻不能允許你的請求。男女婚嫁之事，爻象上說得十分明白，初次婚媾的喜事，應當崇尚厚重的禮聘，這是君子之所重視的人倫之本。如果開頭就不嚴肅慎重地對待，此事終究難以長久。」予成經常心懷詭譎奸詐，於顯祖在位之時，不再向朝廷求婚。太和元年(477)四月，予成派遣使者比拔等人前來向朝廷進獻良馬、貂裘，比拔等人說天朝擁有珍寶華麗之物非常之多，請求讓他們觀看一番。皇帝就令有關官員拿出宮中所藏的珍玩金玉、文繡器物，御廄裡的寶馬、奇禽、異獸，以及人間所用的貴重物品，都陳列在京城街市，讓他們一一觀賞。比拔看了以後，對同來的人說：「大國這等富貴華麗，我一生都不曾見到過。」太和二年(478)二月，予成又派比拔等人前來朝貢，不久又請求通婚。高祖有招納蠕蠕之意，就准許了。予成雖然年年朝貢，卻不曾明確地同朝廷訂立款約，因此通婚之事也就停了下來。
太和九年(485)，予成死。其子豆侖繼位，號伏古敦可汗，是魏人所說「永久」的意思。自稱太平元年。豆侖性情殘暴，殺人成性，他的大臣侯醫西山、石洛候屢次以忠言相諫勸，又勸他與魏和睦相交，不要侵犯中國。豆侖大怒，誣陷石洛候圖謀反叛，把他殺掉，並夷滅其三族。太和十六年(492)八月，高祖派陽平王元頤、左僕射陸睿又同為都督，統領斛律桓等十二員大將率七萬騎兵征討豆侖。蠕蠕部族內高車族人阿伏至羅率十餘萬人向西逃走，自立為主。豆侖與叔父那蓋分兩路追擊，豆侖從浚稽山北面出發向西，那蓋則從金山出發。豆侖多次被阿伏至羅打敗，而那蓋則接連打了勝仗。於是國人都認為那蓋有上天幫助，想要推舉那蓋為首領。那蓋不從，眾人強逼他，他就說：「我當臣子都不行，怎麼能當國主？」部眾就殺了豆侖母子，把他們的屍首給那蓋看，那蓋這才即位。
那蓋號為候其伏代庫者可汗，在魏人語言中是「悅樂」的意思。自稱年號為太安元年。那蓋死，其子伏圖繼位，號他汗可汗，是魏人所說「開端」的意思。自稱始平元年。正始三年(506)，伏圖派使者紇奚勿六跋來朝廷進貢，請求通和。世宗不答覆使者，讓朝廷有關官員下詔書給勿六跋說：「蠕蠕的遠祖社侖是大魏國的叛臣，我們對過去的事予以寬容，暫時與你通使往來。現在蠕蠕已經衰微，勢力比往昔大為減弱，我大魏朝恩德廣厚，興隆如同周、漢，跨據中原之地，肅清八方之外。現因江南尚未平定，權且寬容北邊的擄掠，雙方通和之事，不容輕易應允。如你們整治藩邦之禮，表現出明顯的誠意，自當不會辜負爾之誠心。」永平元年(508)，伏圖又派勿六跋奉上函信一封，並獻上貂裘，世宗不予接納，按照前次曉喻的道理將使者遣還。
伏圖征伐西部的高車族，被高車王彌俄突所殺，其子丑奴繼位，號豆羅伏跋豆伐可汗，是魏人所說「彰制」的意思。自稱建昌元年。永平四年(511)九月，丑奴派僧人洪宣向朝廷奉獻珠寶佛像。延昌三年(514)冬，世宗派驍騎將軍馬義舒出使丑奴，使者還未出發而皇帝駕崩，此事便停止下來。丑奴魁梧健壯，善於用兵。延昌四年(515)，派大臣尉比建前來朝貢。熙平元年(516)，丑奴西征高車並大破高車軍隊，擒獲高車王彌俄突，把他殺掉，吞併所有高車的人馬，其國由此而又趨強盛。熙平二年(517)，丑奴又派大臣尉比建、紇奚勿六跋、鞏顧禮等前來朝貢。神龜元年(518)二月，肅宗駕臨顯陽殿，把鞏顧禮等二十人帶到殿前，派中書舍人徐紇宣讀詔書，表示對蠕蠕履行藩邦之禮不完備的譴責之意。
當初，豆侖被下屬殺死，那蓋繼位為首領，伏圖就佔有豆侖之妻候呂陵氏，生下丑奴、阿那瑰等六人。丑奴即位後，忽然丟失了名叫祖惠的兒子，四處尋找都不見。有個叫屋引副升牟的人，他的妻子名叫是豆渾地萬，年方二十，是一個巫醫，常常假托神鬼附身，以前經常被丑奴所信任，在丑奴那裡進進出出，她說這個小兒如今在天上，我能夠呼叫到他。丑奴母子倆對此十分欣喜，第二年仲秋之際，在大澤中設置帳篷，齋戒潔身七天，祈請上天。過了一夜，祖惠忽然來到帳篷裡，自己說是長期以來住在天上。丑奴母子緊緊抱著他，悲喜交加，於是聚會全國的人，給是豆渾地萬取號為聖女，把她接納為可賀敦，授予她的丈夫屋引副升牟爵位，並賜給牛馬羊三千頭。是豆渾地萬既懷有邪門左道，又頗有姿色，丑奴對她非常喜愛，對她言聽計從，於是國政由此而日益昏亂。像這樣過了許多年，祖惠長大成人，他母親問他早先的事，祖惠說道：「我長期住在是豆渾地萬家裡，根本不曾去到天上，上天的說法是地萬教我的。」他母親就把這些情況全都告訴丑奴，丑奴說：「地萬能夠看得見很遙遠的事情，不能不相信她，你不要用讒言誹謗她。」後來地萬對此感到非常恐懼，就在丑奴面前誣陷祖惠，丑奴就暗地裡把祖惠殺了。
正光初年(520)，丑奴的母親派大臣李具列等人將是豆渾地萬絞死，丑奴大怒，要誅殺李具列等人。這時阿至羅部來侵犯丑奴，丑奴領兵回擊，被打敗。丑奴返回之後，他的母親和大臣把他殺了，立丑奴的弟弟阿那瑰為主。即位僅有十天，阿那瑰的族兄大臣示發率數萬之眾攻打阿那瑰，阿那瑰戰敗，帶領他的弟弟乙居伐輕騎往南投奔大魏。阿那瑰之母候呂陵氏同他的二個弟弟不久就被示發殺死，但阿那瑰卻不知道此事。
同年九月，阿那瑰將要到達京師，肅宗派兼侍中陸希道為主使，兼散騎常侍孟威為副使，到京城轄區的邊地迎接慰勞；派司空公、京兆王元繼到北中這個地方，侍中崔光、黃門郎元纂在離京城五十里處，設置酒宴以表示慰勞，一直把他接到朝廷門闕之下。十月，肅宗來到顯陽殿，指定從五品以上任職顯要的官員、宗室貴族、各藩國的使者貴賓等，都排列坐於殿庭之上，王公以下的人和阿那瑰等人進來後，就在庭院中面北而坐。座位定下來以後，接待賓客的近侍引導王公以下的官員上殿，阿那瑰位置列於藩王之下，又讓將任命的官員和阿那瑰之弟與二叔位列於群官之下。皇帝派中書舍人曹道宣讀詔令表示慰勞和問候，阿那瑰向皇帝啟奏說：「陛下寬厚為懷，讓我的弟弟與叔叔等人得以上殿參與盛會，但微臣還有一位堂兄，在我們部族裡官職高於二叔，乞望陛下允許他上殿。」皇帝下令准許他的請求，就把他的座位安排在阿那瑰弟弟之下，其二叔之上。宴會將要結束時，阿那瑰手捧奏折站立在座席之後，肅宗派舍人常景前去問他有什麼話想要說，阿那瑰請求走到殿前，皇帝令人引導他上前。阿那瑰再次下拜，直身跪著說：「微臣祖先，原是出自大魏國。」皇帝說：「朕已經都知道了。」阿那瑰站起身來說道：「臣的祖先，隨著水草之地放牧牲畜，後來定居在大沙漠之北。」皇帝說：「你的話沒有說完，可以詳細陳述出來。」阿那瑰又說：「微臣的先祖，世世代代居住在北方，雖然山隔水阻，但世代都傾心仰慕大魏的教化；之所以沒有能夠早日普及教化，都是因為高車族的悖逆所致，臣國長期受其騷擾，沒有機會派遣使者前來向朝廷表達我們深遠的誠心。到幾年之前，才逐漸平定高車。我的哥哥當了國主之後，曾經派遣鞏顧禮等使者前來大魏，確實是想要誠心誠意地奉行藩國的禮儀，所以朝廷派曹道芝出使臣國之日，我與當國主的哥哥立即派五位大臣拜受皇帝的詔命。我兄弟二人臣奉朝廷的心願沒有能夠向陛下表明，高車又前來侵犯，國內又有奸臣乘亂反叛，將微臣的哥哥丑奴殺死，擁立臣為國主。僅僅過了十多天，為臣因感到陛下恩慈如同天日，所以在倉卒之間只身前來投奔大魏，歸附聽命於陛下。」皇帝說道：「聽了你的陳說，覺得你還沒有把事理說完，你可以繼續往下說。」阿那瑰再次跪拜接受詔命，起身說道：「微臣因家國有難，隻身來投奔朝廷，我的老母還留在那裡，母子分離相距萬里，本國的臣民都四處逃散。陛下恩德深重，勝過天地，請求陛下派給兵馬，幫助我回歸本國，翦滅叛逆之徒，收集逃散的臣民。望陛下以仁慈為懷，賜給微臣兵馬。我的老母倘若還在人世，能同我相見，就可繼續母子間的恩愛；如果她已經亡故，我定要報這個仇，來洗雪我的奇恥大辱。微臣定當統領餘部，侍奉陛下，對朝廷一年四時的貢納，決不敢有所缺少。臣難以得見陛下聖顏，心裡有許多話要向陛下傾吐，但想要說的意思不是幾句話就能說完的，另外寫有啟奏的表章，現在恭敬地呈送陛下，希望陛下仔細閱覽。」於是把奏折交付舍人常景，把要說的事一一奏上皇帝。不久，肅宗封阿那瑰為朔方郡公、蠕蠕王，並賜給他衣服冠冕，贈給他輕便馬車上的車蓋，以及朝臣的俸祿、儀仗與衛士，待遇與藩王相同。
同年十二月，因為阿那瑰考慮到國內沒有法定的國主，想要回去加以安撫，屢次向朝廷上書請求，肅宗就詔令朝廷大臣商議此事。當時朝臣中意見不統一，有的主張讓他歸還，有的則認為這樣做不妥。領軍元叉時任宰相，阿那瑰私下用黃金一百斤賄賂他，終於獲准回到北方。正光二年(521)正月，阿那瑰等五十四人向朝廷辭別，肅宗親臨西堂，接見阿那瑰及其伯叔兄弟五人，讓他們上殿並賜坐，並派中書舍人穆弼對他們進行慰勞。阿那瑰等人向皇帝拜辭，皇帝下令賜給阿那瑰細明光人馬鎧二副，鐵人馬鎧六副；露絲銀纏槊二張並配有裝飾的白羽毛，赤漆的槊十張也配有白羽毛，黑漆的槊十張並配有旗幟；露絲弓二張並配有箭，朱漆柘弓六張並配有箭，黑漆弓十張並配有箭；赤漆的盾牌六副並有刀，黑漆的盾牌六副並配刀；赤漆鼓角二十具；五色錦被二床，黃綢被褥三十套；諸侯貴戚穿的繡袍一件並帶冠帽，諸侯夫人穿的紅納襖一件；紅袍二十件並帶冠帽，女子穿用的各色絲織物千匹；紅色的小口騎服一套及飾物，紫色的大口騎服一套及飾物；百子帳十八具，黃布幕六張；新鮮乾糧一百石，炒麵粉八石，炒榛粉五石；銅製烏育四個，鐵製烏育二個，容積為二斛；黑漆的竹木盍四個，容積為二升；婢女二人；父草馬五百匹，駱駝一百二十頭，母牛一百頭，羊五千頭；朱紅色漆畫的盤子十合；小米二十萬石。全都運送到目的地交給阿那瑰。又詔令侍中崔光、黃門元纂把他們送到京城之外。
阿那瑰前來投奔朝廷之後，他的堂兄大臣婆羅門率領數萬人征討示發，把他打敗。示發只得逃奔地豆於人，被地豆於人殺死。於是蠕蠕人推舉婆羅門為國主，號為彌偶可社句可汗，是魏人所說「安靜」的意思。當時，安北將軍、懷朔鎮將楊鈞給朝廷上表說：「傳說蠕蠕人已經另立國主，是阿那瑰的堂兄。北夷人心似野獸，他既然已即國君之位，恐怕未必會以一個殺死兄弟的人的身份，出郊隆重地迎接其堂弟阿那瑰。我朝輕率地送他前去，徒勞往返，將會徒然損害國威，除非是增派軍隊，否則就不可能把他送回北方。」同年二月，肅宗讓昔日擔任蠕蠕使者的牒雲具仁，前往曉喻婆羅門勸其迎接阿那瑰以恢復其王位。婆羅門特別驕橫侮慢，毫無遜位迴避之心，強迫牒雲具仁對他以君臣之禮相見，具仁堅守節操不肯屈服。婆羅門就派他手下的大官莫何去汾、丘升頭等六人率兵二千人隨具仁迎接阿那瑰。五月，牒雲具仁回到阿那瑰所在的邊鎮，一同計議當時的事態形勢。阿那瑰顧慮重重不敢北進，就上表請求仍回到京都。適逢婆羅門被高車族追逐，被迫率領十個部落到涼州歸降大魏，於是蠕蠕族數萬臣民相率迎接阿那瑰。七月，阿那瑰上書啟奏說：「歸順的蠕蠕人元退社、渾河旃等二人本月二十六日到達我的鎮所，說蠕蠕國內大亂，各個姓氏另居別地，相互之間抄家搶掠，如今北方部族的人都引頸翹望，等待朝廷前來拯救。現在我請求朝廷依照先前的恩德，賜給精兵一萬。並令人督率送微臣前往漠北，撫慰安定百姓，倘蒙陛下應允我的請求，事情必定能夠成功。」肅宗詔令將此事交付尚書、門下省便為計議。八月，皇帝詔令兼散騎常侍王遵業馳往驛所宣旨慰問阿那瑰，並且再次對他進行賞賜。
同年九月，蠕蠕後主俟匿伐前來投奔懷朔鎮，俟匿伐是阿那瑰的哥哥，他一再聲稱蠕蠕人希求朝廷派兵，並敦請阿那瑰歸國。十月，錄尚書事高陽王元雍、尚書令李崇、侍中侯剛、尚書左僕射元欽、侍中元叉、侍中安豐王元延明、吏部尚書元..義、尚書李彥、給事黃門侍郎元纂、給事黃門侍郎張烈、給事黃門侍郎盧同等人上書啟奏說：「臣等私下聽說漢朝在匈奴分立南、北單于，晉朝則有東、西單于之稱，都是為了相互維繫抵禦外患，為國家建立屏障。現在臣等參與議論，認為懷朔鎮在北國名叫無結山吐若奚泉，敦煌北部的西海郡就是漢、晉兩朝舊有的屏障，這兩處地勢寬闊平坦，原野廣袤肥沃。最好是把阿那瑰安置於西吐若奚泉，把婆羅門安置在西海郡，命他們各自統轄所在的部落，收聚離散的百姓。他們的爵號和所需物資給養，可憑朝廷的恩德予以裁斷處置。他們大臣以下各級官吏，還讓其依照原有的習慣任命。阿那瑰所居之地，既然位於邊境之外，應盡量少給優厚的遣送，以顯示朝廷威嚴的治理。請詔令沃野、懷朔、武川三鎮各派二百人，令各鎮軍隊的主將監督率領，給他們配給糧草兵器，送阿那瑰到達西吐若奚泉，仍留在那裡幫助他從事創建事宜，成功之後再讓他們回來。從北邊前來歸順婆羅門的人，令各州鎮官員依照規定供給口糧，把他們送到懷朔阿那瑰那裡，由各鎮和使者酌量給以糧食。尚在京城的人則聽任他們自己決定去留。阿那瑰還處於初創時期，原先沒有儲備積蓄，請給予朔州麻子乾糧二千斛，由官家駝隊運送前往。婆羅門居於西海郡，既然是地處邊境之內，物資和軍隊的供給就不能與阿那瑰一樣對待。阿那瑰等新建藩國，應當各派使者持節乘驛馬迅速趕到那裡予以慰問撫喻，並委付使者幫助他們籌劃、治理。」肅宗准許了他們所奏之事。十二月，皇帝詔令安西將軍、廷尉元洪超兼任尚書行台，到敦煌安置婆羅門。不久，婆羅門與他的部眾圖謀反叛投奔口厭噠國，口厭噠國君的三個妻子，都是婆羅門的姊妹。後來還是州軍前去征討，擒獲婆羅門。
正光三年(522)十二月，阿那瑰上表請求朝廷供給小米用來做種子，皇帝詔令供給萬石。四年，阿那瑰的部族遇到大饑荒，就進入邊塞大肆搶掠，肅宗令尚書左丞元孚兼任行台尚書持節前往曉喻。元孚見到阿那瑰，被他扣押，他把元孚當作人質帶在身邊，驅使部下搶掠良民二千人及公私驛馬牛羊數十萬向北逃遁，向元孚道歉之後把他放回。肅宗詔令驃騎大將軍、尚書令李崇等人率十萬騎兵討伐阿那瑰，出邊塞三千餘里，直到大沙漠，沒有追到阿那瑰，只好撤回。俟匿伐來到洛陽，肅宗駕臨西堂，接見俟匿伐。正光五年(524)，婆羅門死於洛陽南邊的客館中，皇帝詔令追贈他為使持節、鎮西將軍、秦州刺史、廣牧公。
這一年，沃野鎮人破六韓拔陵反叛朝廷，各鎮與他相呼應。孝昌元年(525)春，阿那瑰率兵征討破六韓拔陵，肅宗詔令派牒雲具仁送去各種雜物慰勞賞賜阿那瑰，阿那瑰拜受皇帝詔命，率領十萬之眾，從武川鎮向西進軍沃野，屢戰告捷。四月，肅宗又派兼通直散騎常侍、中書舍人馮俊出使阿那瑰，表示慰勞並按照次第等級給以賞賜。阿那瑰的部落已經安定，兵馬略為強盛，於是自號敕連頭兵豆伐可汗，是魏人所說「把攬」的意思。十月，阿那瑰又派郁久閭彌娥等人前來朝貢。孝昌三年(527)四月，阿那瑰派使者鞏鳳景等前來朝貢，在他們臨走時，肅宗下達詔書說：「北方各鎮的夷狄，不停地背叛朝廷，蠕蠕國主為大魏國盡忠，幫助朝廷誅討叛逆，表示侍奉朝廷的誠心，不忘寢食之恩。現知他停息在北方邊陲，與..朱榮相鄰接，應嚴格管束部屬，不要施暴擄掠。再者，最近又得蠕蠕主的奏啟，再次要為國東征。但考慮到蠕蠕主世代居住北漠，不適應夏季炎熱，現在可暫且停止，等待以後的敕令。」這是朝廷考慮他反覆無常的原因。此後，蠕蠕主頻繁派遣使者前來朝貢。
建義初年(528)，孝莊帝下詔說：「功勳卓著的人應得重賞，德行厚重的人名聲隆盛，蠕蠕主阿那瑰鎮守防衛於北部邊境，抵禦敵侮於北方地域，終於使得陰山一帶戰亂停息，弱水一帶沒有戰事，事跡刊刻在狼山，功名銘記於瀚海，至誠之心甚為深厚，功勳業績未得酬報。所以應當對他表示特殊的禮遇，怎能用普通的規格來對待他。從今以後，他來朝廷贊拜可以不稱道自己的姓名，給朝廷上書可以不稱臣。」太昌元年(532)六月，阿那瑰派烏句蘭樹什伐等前來朝貢。並替自己的長子請求娶一位公主為妻。永熙二年(533)四月，出帝下詔把范陽王元誨的長女琅笽公主許配給阿那瑰的長子，還沒有舉行婚禮，皇帝就被迫逃往關中。齊獻武王派使者前往遊說阿那瑰，阿那瑰就又派使者來朝貢，並再次求婚。獻武王正要招撫四方邊遠之地，就把常山王之妹樂安公主許配給他，改稱為蘭陵公主。阿那瑰送奉一千匹馬作為聘禮，迎娶公主，皇帝令宗正元壽送公主前往北地。自此以後，蠕蠕向朝廷的朝貢就連續不斷而來。阿那瑰因見齊獻武王的威德日益隆盛，就請求把自己的愛女送給他，靜帝詔令獻武王接納她。從此之後，北方邊境地區就沒有戰亂騷擾的現象發生了。