苻坚闻言大悦，采纳了燕凤的建议。于是拓跋珪又回到了代北，并跟母亲贺氏一起投身于独孤部，在刘库仁的羽翼下度过了七八年。
后来苻坚淝水战败天下复又大乱，而刘库仁死后他的儿子刘显又想谋害拓跋珪，贺氏不得不带着儿子投了自己的娘家贺兰部。他舅舅贺讷见拓跋珪已经长成了一个英武少年，不禁又惊又喜，道：“大王有孙如此，复国之后，你可别忘了老臣！”拓跋珪笑道：“若果真如舅舅所言，甥不敢忘也。”
第二年（386）春天，在贺兰部和拓跋部旧臣长孙嵩、叔孙普洛等人的支持下，拓跋珪大会于牛川，即代王位，不久又改国号为魏，北魏政权自此始。
这时，拓跋珪还未满十六岁。