當拓跋珪和後燕殊死戰鬥之時，躲在他後方的一些遊牧民族開始蠢蠢欲動，不斷出兵襲擊他的老巢，這令拓跋珪非常惱火。
擊敗後燕後，拓跋珪就開始考慮如何對付這幫難纏的遊牧民族，其中最活躍的就是高車，於是拓跋珪決定先拿它開刀。登基大典後的第二年（天興二年，399年）正月，拓跋珪就迫不及待下令出兵北伐，向高車發動進攻。
為了儘快消滅高車主力，拓跋珪故技重施，再次兵分三路：
命大將軍常山王拓跋遵等三軍自東道出長川；
鎮北將軍、高涼王樂真等七軍從西道出牛川；
拓跋珪自領中軍從中道出塞襲擊高車；
這次出兵非常順利，各路軍只用了一個月便取得了巨大戰果，到二月時已經擊破高車30餘部，俘虜7萬多人，馬30萬匹，牛羊140萬頭，極大地震懾了高車諸部。
當然此戰中也有一些漏網之魚逃往大漠深處，秉承除惡務盡的原則，拓跋珪派遣衛王拓跋儀領兵三萬越過大漠追擊，在戈壁深處打了個漂亮的殲滅戰，俘獲2萬人，馬5萬匹，牛羊20萬頭，車2萬乘，戰利品堆積如山。
經過這次遠端作戰，高車的勢力受到沉重打擊，元氣大傷，高車諸部紛紛投降北魏。雖然還有一些部落拒絕投降，但終拓跋珪一世他們都不敢再南下侵擾，保持了低調。
高車的氣焰被壓下去後，柔然趁機跳了出來，這次北伐柔然也有損失，不過很輕微，並沒有傷筋動骨。這幫人很快將取代高車，成為北魏最強勁的對手。
柔然顯然比高車更難對付，北魏此時也沒有消滅柔然的能力，只能加強邊境防備，以防守為主。
回過頭來說說那個死硬反魏分子劉衛辰，這段時間拓跋珪忙於征討後燕，沒時間搭理這個令人頭疼的傢伙，劉衛辰趁機再度出兵襲擾北魏。劉衛辰一直活躍在對抗北魏的第一線，這引起了西燕慕容永、後秦姚萇等人的注意，他們紛紛伸出橄欖枝向劉衛辰示好，對他加官進爵，都想把他拉到自己的陣營去。
這樣一來，劉衛辰就更得意了，頻頻出兵襲擾北魏，史書稱其“累為寇害”，成為北魏的心腹大患。
趁著拓跋珪無暇顧及，劉衛辰派兒子直力鞮率八九萬騎兵進犯南部，將拓跋珪包圍在鐵岐山。當時拓跋珪身邊只有五六千人，形勢危急，拓跋珪鎮定自若，命令士兵將戰車擺成營壘，沉著應戰，居然打敗了直力鞮，虜獲牛羊二十萬頭。這個好訊息令拓跋珪龍心大悅，決定乘勝追擊，一鼓作氣追入劉衛辰的地盤。
大軍在五原金津渡過黃河，直奔劉衛辰的老巢而去，當地的居民聞訊四散而逃，劉衛辰父子聽說拓跋珪大軍逼近悅跋城，也沒心思抵抗了，撒丫子就跑。
陳留公拓跋虔追到白鹽池，俘獲了劉衛辰的老婆孩子，將軍伊謂追到木根山，活捉了劉衛辰的兒子直力鞮，並將他的死黨一網打盡。就剩下劉衛辰孤身一人倉惶逃脫，結果還是沒能跑出去，半路上被譁變的部下所殺，腦袋被送到拓跋珪的行宮請功，另外還繳獲了牛羊馬四百餘萬頭，這是一個非常龐大的數字，足見劉衛辰的財大氣粗，家底雄厚。
據說劉衛辰在逃跑途中經過一條河時，發現河水居然全變成了血紅色，這詭異的一幕令他非常厭惡，認為是不祥之兆。果然沒過幾天，他便死於部下之手，他的五千親信黨羽也全部被拓跋珪處死，拋屍河中，河水果然變成了血紅色，應驗了幾天前的那一幕。
五千人被殺，血染河水，這下鐵弗部算是和拓跋部結下了血海深仇，最關鍵的是劉衛辰的一個兒子劉勃勃竟然躲過了一劫，撿了一條命，投奔薛幹部的首領太悉伏去了。
沒有人會想到，這條毫不起眼的漏網之魚後來會成為北魏最強勁的對手，一直到幾十年後北魏不得不傾盡全力和他上演了一場慘烈的決戰，當然這都是後話了。
那個時候，這條漏網之魚已經不叫劉勃勃了，他給自己起了一個嶄新的名字——赫連勃勃。
此時拓跋珪的主要精力還是在中原方向，後燕雖然被他擊敗了，但局勢還很混亂。除了各地後燕殘軍的反抗外，關中的後秦也趁火打劫奪取了原來西燕控制的河中地區（今山西運城一帶）。另外還攻佔了晉朝故都洛陽，其勢力範圍最遠時甚至到達了徐州一帶，這對北魏構成了嚴重威脅，拓跋珪不能坐視不理。
這後秦也是十六國之一，由出身羌族的姚萇建立。
早期姚萇的部落臣服於前秦，淝水之戰後，前秦陷入四分五裂，臣服前秦的各個部族紛紛自立為王。姚萇也加入了這一洪流，於384年佔據北地（今陝西富平）自稱秦王，第二年擊殺前秦皇帝苻堅，攻佔長安，自稱秦帝。為了和前秦區分，後世稱他的政權為後秦。
姚萇是和拓跋珪同年稱帝的，都是386年，這一年在北魏是登國元年，在後秦是建初元年。拓跋珪定都平城（今山西大同），姚萇定都長安（今陝西西安），為了避自己的諱，姚萇改長安為常安，指派太子姚興留守長安，自己帶兵追擊前秦餘孽苻登等人，一口氣追到隴西安定，大敗苻登，掃清了這股殘敵。
然而就在回師途中，姚萇卻突然病倒，夢到了被他殺死的前秦皇帝苻堅帶領鬼兵找他索命，姚萇驚嚇過度，醒來後病情愈發沉重，最終不治身亡。
姚萇死後，太子姚興即位，改元皇初。姚興是姚萇的長子，稱帝后沒過幾年便宣佈取消皇帝稱號，降為天王。這個略顯奇怪的頭銜後來又出現過兩次，分別是北周孝閔帝宇文覺和太平天國的洪秀全。
姚興也是一個頗具進取心的君主，消滅苻登後，他的目光便投向了函谷關以東的那片土地，那裡是中原，自古號稱兵家必爭之地。他若想東進爭奪天下，就必須先拿下那裡，而首當其衝的就是魏晉故都——洛陽。
洛陽經歷了八王之亂和匈奴人的輪番蹂躪，早已喪失了政治中心的地位，在連年的戰亂中淪為一座廢墟。姚興很輕鬆便攻下了洛陽，留下弟弟東平公姚紹鎮守，他自己率軍攻打佔據甘肅一帶的乞伏乾歸，奪取了他的地盤。
乞伏乾歸是十六國之一西秦開國之君宣烈王乞伏國仁的弟弟，也是西秦的第二位君主，諡為武元王。
乞伏乾歸不是姚興的對手，被打得大敗而逃，先是投奔南涼，後又輾轉投降後秦。
擺平了乞伏乾歸後，姚興還沒來及高興便突然接到了軍情急報，朔方出事了。
他的競爭對手拓跋珪突然出兵攻打他的寵臣高平公破多羅沒弈幹，沒弈幹一看自己不是拓跋珪的對手，丟下軍隊自己跑路了，只帶領幾千親兵連夜逃回了長安。
姚興很生氣，後果很嚴重。
那麼拓跋珪為什麼要突然攻打沒弈幹呢？
這事兒呀，歸根結底還是赫連勃勃……。呃，此時還叫劉勃勃，是劉勃勃惹出來的。
