北魏平定了关中和陇右，但其统治并没有预想的那么稳固。这些地区半个世纪以来都是前后秦和夏国的势力范围，大量匈奴人、氐人、羌人聚居在这里，与入关后的鲜卑人冲突不断。北魏延和年间（公元432年至434年），陇右地区的匈奴休屠部人和羌人屡次起兵，令拓跋焘十分头疼。拓跋焘调用强将守卫重镇，前往镇压，仍不足以平定乱况。皇帝本人于延和三年（公元434年）领兵亲征，勉强将势力并不十分强大的休屠部人制服，这一带各地镇将的相互攻伐才告一段落。
（关东自前燕以来，除却前秦苻坚短暂的十几年统治时期，一直是鲜卑人称大，至此已有八十多年，所以拓跋氏即使是统一了北方，其统治重心也没有离开过冀、并、幽这几个州，关东的人口与重要程度也远大于关中。关中的问题，崔浩早就对拓跋嗣分析过，即“华、戎杂错”，民族矛盾远较关东复杂，如果说北魏在关东需要重点解决的是鲜卑人与汉人的对立问题，那么在关中不但要解决胡汉之间的对立，还要解决各胡之间的对立，十分头疼。关中成为北魏统治的薄弱环节，一直到一个世纪后北魏分裂、东西魏争战时期也没有改变。有趣且略带讽刺的是，南北朝的最终统一却反而是由来自于关中的军事势力完成的，此乃后话。）
关中之外，匈奴人还有一个主要活动区域，那就是山西的并州地区。刘渊的汉国当年从此起家，一百多年后以前的匈奴人已经散落中原各地，在他们的大本营最为活跃的，是所谓“山胡”。
山胡，也称稽胡、步落稽，是一支族源比较难考的胡人。按照正史的说法，山胡是刘渊南匈奴五部的苗裔，但也有人认为他们是春秋时期就活动于陕西北部的山戎、赤狄的后人，还有人认为山胡中可能还夹杂着西域人种，血统非常复杂。北魏时期，山胡在今天的山西、陕西两省的北部部落繁多，居住于山谷之间，一度是北朝内部的隐患，北魏末年更是掀起了大规模起义。由于他们的活动区域较大，且易守难攻，北魏统治者对付他们并不轻松。
拓跋焘在解决了关中诸胡之乱后，移师隰城（今山西汾阳），想乘胜把山胡也给摆平。他命阳平王拓跋它督领大军进击山胡首领白龙，自己则带了几十骑登上附近山头观战。山胡虽然不是什么正规军，但却熟悉地形，也懂得擒贼擒王的道理。白龙在山中的十几处险要之地埋伏了部下，拓跋焘的小队伍一经过，就忽然杀出，围攻拓跋焘。拓跋焘坠马，几乎被擒，亏得贴身侍卫挺身而出，与山胡人展开肉搏，连杀数人，才保护拓跋焘脱身。这也使得拓跋焘不敢再轻视这些隐蔽在山中的敌人，北魏军队与山胡仔细周旋，终于大败山胡部众，斩杀白龙。
搞定了这几场内部的小乱，拓跋焘又要率领大军北伐柔然了。
柔然在吴提继位可汗后（参见《元嘉之治》），军事力量一蹶不振，主动遣使求和，拓跋焘正忙着对付其他的外敌，也不为难吴提，同意双方和亲：拓跋焘把西海公主嫁给吴提，吴提则送来了自己的妹妹，到北魏宫中做左昭仪，同时还让自己的哥哥秃鹿傀献上两千匹好马，拓跋焘龙颜大悦，也赐给柔然不少东西。
友好的关系并没有持续多久，仅过两年，吴提就单方面断绝关系，举兵犯塞（也不管自己妹妹死活了）。拓跋焘无比震怒：柔然果然是头白眼狼，只能靠拳头来教训他。太延四年（公元438年），拓跋焘亲率大军从五原北伐，乐平王拓跋丕与永昌王拓跋健各督十五员战将出东西两路，拓跋焘的主力则为中军，从浚稽山（今蒙古土拉河、鄂尔浑河上游以南一带）一直走到天山。这一次吴提早听到了风声，提前往西北逃窜，魏军登上白阜山（今蒙古抗爱山脉西北），不见柔然踪影，回军途中碰上漠北大旱，一路没有水草，行军艰难，人马大多饥渴至死。
吴提很是得意，派了使臣到西域、北凉等地散布谣言：“魏国天子亲自来打我，可怜士兵马匹疾疫而死，大败而回呀，他弟弟拓跋丕还被我生擒活捉了。现在魏国已经衰弱，天下以我柔然最强，以后你们这些国家也不用恭迎魏国派来的使者了。”
北魏在灭掉夏国以后一直与西域通使，尤其是通过西域各国的宗主国北凉进行各方面的交流。现在听说北魏吃了败仗，这些小国都不愿意搭理它了，北凉更是大为怠慢。沮渠蒙逊的继位者沮渠牧犍与嫂子李氏私通，兄弟一起搞群交，后宫简直混乱不堪。李氏嫉恨牧犍的正室夫人——北魏与北凉和亲时拓跋焘嫁过来的妹妹武威公主，便拉了牧犍的姐姐一同在公主的食物中下毒。拓跋焘闻讯，急派御医去给公主解了毒，李氏的阴谋没能得逞。拓跋焘命沮渠牧犍交出李氏，牧犍不理，只把嫂子安置在酒泉，还拨了一笔钱给她花销。
拓跋焘明白若不消灭北凉，难以慑服西域各国，便与崔浩商量。崔浩指出沮渠牧犍叛心已露，不可不诛。北伐柔然虽因非战斗减员，但主力尚存，凉州弱小，伐之必克。拓跋焘大为赞同，又在殿上召集群臣商议。
北魏刚吃了没有水草的亏，弘农王奚斤等人反对出征，说：“沮渠牧犍小国而已，虽有不臣，但还是向我们称藩的。我国刚打过仗，需要休整。而且听说他们那里土地荒凉，没有水草，沮渠牧犍若再坚壁清野，大军一到，怕是会重蹈北伐的覆辙。”
尚书古弼、李顺等人也说：“姑臧城（北凉国都）百里之内，都是不长草的荒地，只有城南山上积雪融化流下的水以供灌溉。我军若去讨伐，他们决断渠口，我们兵马不就都渴死了么，奚斤大人所言极是，万万不可西征啊！”
李顺和崔浩一样是汉人，父亲一代就从后燕投靠了北魏，曾多次作为使者被拓跋焘派往凉州，显然关于凉州的话题他应是最有权威的，偏偏崔浩不信他。
崔浩与李顺是儿女亲家，崔浩的弟弟娶了李顺的妹妹，而弟弟的儿子娶的又是李顺的女儿。按理说关系应该很铁，可是崔浩就是有些自大，看不起李顺，两个人之间矛盾很大。崔浩当面反驳说：“《汉书·地理志》里就有说了：‘凉州之畜，为天下饶。’要是那里没有水草，怎么放牧啊？而且汉人的居住地，历来就是依水草筑城。积雪融化的水，足够引来灌溉么？你说的根本就是谎言，经不起推敲。”
李顺急得面红耳赤，辩道：“耳闻不如目见，我是亲自看见的，你凭什么跟我辩？”
崔浩冷笑：“我看你是收受了人家的钱财，为他们说话吧，别以为我没亲眼看见就好欺骗！”
李顺果然心虚，一个字也说不上来了。他出使北凉时，沮渠蒙逊曾给了他不少好处。回来后，他就上下打点文武大臣，传播“凉州无水草”的言论。崔浩的一句话戳穿了李顺的谎言，坚定了拓跋焘西征的决心。
太延五年（公元439年），拓跋焘把太子拓跋晃留在平城监国，大将军、长乐王嵇敬与辅国大将军、建宁王拓跋崇以两万人屯兵漠南，防备柔然，然后自领大军从平城出发，浩浩荡荡，开往凉州。师出有名，他又命手下人拟了一份罪状，斥责沮渠牧犍的叛逆行径，劝他早点投降，以保性命。
北魏这次进军，还找到了一位好向导，那就是南凉的最后一代君主秃发傉檀之子秃发破羌。南凉灭亡后，秃发破羌投奔北魏，拓跋焘欣赏他仪表堂堂、行事机敏，赐他爵位，并封为将军。秃发氏与拓跋氏同源，拓跋焘又赐姓名“源贺”。源贺对拓跋焘说：“姑臧城本被我秃发氏占据，现在城外有四部鲜卑，都曾是我父亲的臣民。我愿领兵在前，宣扬我们大魏的军威，那些旧部必然来降。到时我们再围攻姑臧孤城，取之易如反掌。”魏军依计行事，很快招降了河西大部军马，数万部落，牲畜十几万。
沮渠牧犍被孤立，只得固守姑臧，派人向柔然求救。柔然可汗吴提吹牛虽然不打草稿，真打起仗可不怎么行。他领兵犯塞，遭遇北魏司空长孙道生拒守，兄长企列归又在阴山北面被嵇敬、拓跋崇击破。吴提不仅没帮成北凉，还害得自己损兵折将，远遁漠北。
拓跋焘来到姑臧城下，眺望四野，水草丰盛，心中赞服。他兴奋地对随军的崔浩说：“爱卿所言，果然应验。”崔浩答道：“微臣不敢不说实话，倒是那个李顺，接收了沮渠牧犍父子的贿赂，欺骗陛下，几乎误国。”拓跋焘原本还挺宠信李顺，经过这一连串事件，开始厌恶李顺。崔浩乘机在他耳边说些李顺的坏话，又有凉州人告发李顺受贿的实据，拓跋焘终在三年后下令将李顺斩首。（崔浩的谋略屡屡成功，是拓跋焘信任他的主要原因，但他利用这些公报私仇，对李顺极尽打击报复之能，把人往死路上逼，就不够厚道了。所以崔浩虽然见识非凡，在北魏朝中却结怨颇深，为拓跋氏谋了一辈子还是惹了杀身之祸。）
沮渠牧犍内外交困之下，带文武百官面缚出降，凉州入于北魏版图，沮渠氏的北凉灭亡。（沮渠氏政权还有个小小的尾声，牧犍的两个弟弟无讳和安周逃到西域，攻占了高昌国，多熬了那么二十几年，终灭于柔然之手。）
几年后，北魏又攻占了宋、魏之间氐人建立的仇池。鲜卑人成为北方博弈的最后胜者，除北魏以外所剩的两大势力：柔然和吐谷浑，也都是鲜卑的旁支或苗裔。