拓跋珪恢复代国，但这个国号是晋朝给的，拓跋珪肯定不情愿，史书记载他复立代国没多久便启用国号魏，但对于尚处游击状态下的拓跋珪，国号是什么根本不重要，重要的是如何活下去。实际刚复立的代国也仅是拓跋珪所属部众口头上的“国家”，没设置相关朝廷机构，只是几部首领跟随拥护。在中原长大的拓跋珪思路比刘显、贺兰部等理念还是相对超前的，游牧不解决根本，需要发展农耕，有稳定的根据地。于是拓跋珪将根据地迁移到定襄（今山西省忻州定襄县附近，发展农耕、休养生息。

公元386年，刘显看到拓跋珪似乎是仅仅依靠血脉便可以拥兵自重，于是刘显派弟弟去慕容永那里接回拓跋窟咄。如果不算拓跋珪，拓跋窟咄便是拓跋什翼键最小的儿子，并且与拓跋珪一样在长安当人质，后来随慕容永逃出长安，担任西燕的新兴（大致今山西省忻州市所辖范围太守。当时新兴郡的治所就在定襄附近，拓跋珪阵中的人马躁动起来，时不时出现反叛。无奈之下，拓跋珪再次投奔贺兰部，同时向慕容垂求援。

慕容垂派其子慕容麟救援拓跋珪。慕容麟大军未到，拓跋珪阵中乱作一团，身边不时冒出些要暗杀拓跋珪的人，好在拓跋珪拥有天命，一次次躲过危险。慕容麟知道部队行进到拓跋珪那还得些时日，于是打发拓跋珪的使者赶紧回去，说是大燕援军马上就到。果然拓跋珪看到回来的使者，军心算是安定了下来，恢复了不少士气，抵挡住了拓跋窟咄的进逼。不久，慕容麟与拓跋珪会合，一仗就把拓跋窟咄杀得大败，拓跋窟咄逃到铁弗匈奴刘卫辰那里，刘卫辰将拓跋窟咄杀死。当年刘卫辰被拓跋什翼键打的几乎灭国，投靠苻坚后反而借助前秦军力灭掉代国，这两家可以说是世仇。

前秦没有了，刘卫辰打算和慕容垂通好，送马三千匹给慕容垂。公元387年，送马的队伍，路过刘显的地盘，刘显打败押送的军队，掠取马匹后离去。慕容垂很生气，再次派遣慕容麟等率军讨伐刘显。这次战斗拓跋珪也参与了，跟随慕容麟大败刘显，刘显逃奔到马邑（今山西省朔州市附近西部山中。慕容麟继续率领轻装骑兵追击刘显，最后刘显逃到长子投奔西燕慕容永，他的部众全部投降慕容麟，或许拓跋珪也收去了些，独孤部被灭。在后燕的辟护下，拓跋珪的根据地进一步得到巩固，基本恢复了拓跋什翼犍时期的代国地盘，甚至收获了相对精良的整装部队，可以说是他复国以来的第一桶金。

击败独孤部后，根据史书记载，拓跋珪继续征讨周围部族。公元389年，拓跋珪率军讨伐叱突邻部，他的两位舅舅，贺兰部的贺讷和贺染干反叛，率领部族去解救叱突邻部，结果被拓跋珪击败，贺兰部西逃。第二年六月，铁弗部刘卫辰派其子刘直力鞮攻打贺讷，贺讷不敌刘直力鞮，向拓跋珪求救，拓跋珪率军击败刘直力鞮。之后，拓跋珪将贺兰部迁徙到国境东边，与后燕接壤。后来，贺讷与后燕慕容垂通和，慕容垂封贺讷为归善王。贺染干想要杀贺讷自立，于是贺讷与贺染干相互攻击。慕容垂派其子慕容麟率军攻打，先后击败贺讷与贺染干。拓跋珪率军解救贺讷，慕容麟只得撤军。之后，贺兰部便彻底归附拓跋珪。

史书中的拓跋珪圣人附体，虽然舅舅贺讷拥立有功，但与另外一位舅舅贺染干一起，屡次背叛拓跋珪，拓跋珪又屡次救援他们。而在之前拓跋珪有危险时，仅是记录去舅舅家躲避，丝毫没有舅舅们出兵相助的记录，似乎有些说不过去。铁弗部刘卫辰早先投靠苻坚，后来投靠慕容垂，拓跋珪尚处于草创阶段，似乎不能凭一己之力跨过慕容垂而击退刘卫辰。贺染干早先便有杀掉拓跋珪自立为王的想法，全靠拓跋珪生母的周旋和贺讷的支持。

或许还有另一个版本。拓跋珪击败拓跋窟咄之后，慕容垂封他为西单于、上谷王，史书记载拓跋珪拒绝了，但凭他当时的实力，他没有拒绝的资本。上谷在今河北省张家口怀来县东南附近，可以说是雁门关外的草原地区出入蓟城，向东通往幽州的咽喉之地。上谷以及附近代郡的太守反叛，归附刘显，慕容麟及尾随在后面的拓跋珪讨灭刘显之后，慕容麟把其部众迁出，这两个郡的建制一并撤销，成为无主之地。后燕眼中的无主之地对于拓跋珪来说是一片沃土，这个区域离之后北魏的龙兴之地平城（今山西省大同市很近，如果利用上谷王的封号对于拓跋珪招纳人马有很大的好处。后来拓跋珪征讨高车部落，高车是后来北朝人对这个部落的称呼，东晋对他们称作丁零，拓跋珪当然是为了讨好正在平叛翟氏丁零的慕容垂。而这个高车部落与贺兰部关系相当之好，拓跋珪讨伐高车便是与舅家翻脸，贺兰部也顾不得那么多情面，于是与拓跋为敌，开始进攻拓跋珪。拓跋珪自己邀功不成反而桶出篓子，再次向舅爷慕容垂求援，慕容麟击败贺兰部，将其赶至勿根山（今内蒙古乌兰察布兴和县西北附近。贺衲向后燕投降，把弟弟贺染干送到中山当人质，他的部众被调遣到上谷。又是上谷，这个地方按理说已经没人了，似乎把贺兰部迁到那里没什么用，不会没用的，并且相当有用，因为拓跋珪在那里，拓跋珪成功收入贺兰部。之后拓跋珪或许是以铁弗匈奴的威胁为借口，将贺衲的部落向东迁移，更加的靠近做人质的贺染干。贺染干看到哥哥到来，便谋划的杀掉哥哥让自己真正成为贺兰部的首领，贺衲得知后率先对贺染干发起攻击。拓跋珪将这条消息报告给慕容垂，慕容垂再次派出慕容麟，在拓跋珪向导的带领下，贺衲被活捉，其部众向后燕投降，贺染干被押送回中山，贺兰部终被平灭。

铁弗部的刘卫辰不忍拓跋珪做大，公元391年十月，刘卫辰派其子刘直力鞮率军九万人侵入拓跋珪势力范围内的南部地区。十一月，两军在铁岐山（今内蒙古包头固阳县西北以南决战，拓跋珪将刘直力鞮打得大败，刘直力鞮单骑逃走。不久后，拓跋珪从五原金津（今内蒙古巴彦淖尔乌拉特前旗东南附近向南渡过黄河，径直进入刘卫辰的辖区。刘卫辰部落惊骇异常，顿时大乱，十一月二十二日，拓跋珪直接抵达刘卫辰所居住的悦跋城（今内蒙古鄂尔多斯市东胜区西泊江海子乡大成梁古城，刘卫辰父子仓惶逃走。拓跋珪分别派遣将领率领轻装骑兵追击，在木根山（今内蒙古鄂尔多斯鄂托克前旗南北大池一带生擒刘直力鞮，刘卫辰则被其部下杀死，其余的全部被拓跋珪下令诛杀，共计五千余人，拓跋珪将这些人的尸体全部扔进黄河，仅有其幼子刘勃勃逃脱。

史书记载拓跋珪独自带队，平灭强大的铁弗部，得到数以百万计的牛羊马，实力大增，但这其中或许免不了慕容麟的帮助。在此之前，拓跋珪向北痛击柔然并使其臣服，将其部落迁移至云中郡（今山西省大同市附近。接连不断的胜仗使拓跋珪逐渐有了自立的想法，而他的中原的宗主国后燕也越来越觉得拓跋珪是个祸患。