帝王之兴也，
必有积德、累功、博利……
（北魏）终于百六十载，
光宅区中（即中原地区）。
其原固有由矣。
——《魏书·序纪》后史臣之语
关于拓跋鲜卑的早期历史与风俗状况，《魏书·序纪》载云：
昔黄帝有子二十五人，或内列诸华，或外分荒服。昌意少子受封北土，国有大鲜卑山，因以为号。其后世为君长，统幽都之北，广漠之野，畜牧迁徙，射猎为业。淳朴为俗，简易为化，不为文字，刻木纪契而已，世事远近，人相传授，如史官之纪录焉。
将自己族群的始祖归为黄帝之子，显然是北魏史官杜撰出来的无从查考的附会之说，为非华夏族政权回溯历史的习惯作法。把自己的族系归为黄帝的后裔，自然与华夏（汉）族人士殊途同源，找到了血缘与文化求同的“根脉”。至于其原始发祥地，《魏书·序纪》称其“国中有大鲜卑山，因以为号，”与其他种类的鲜卑人传说如出一辙，而“大鲜卑山”的准确方位却难以确定，通常以大兴安岭北段当之。
拓跋鲜卑的迁徙历程充满了传奇色彩。经过研究者的多年探索，拓跋鲜卑的早期发祥地被确定在遥远的大兴安岭北部的“嘎仙洞”。这一发祥地便是古代文献中的所谓“鲜卑石室”。
《魏书·乌洛侯国传》有着“鲜卑石室”来历较详细的记载：
世祖真君四年（乌洛侯国使者）来朝，称其国西北有国家先帝旧墟，石室南北九十步，东西四十步，高七十尺，室有神灵，民多祈请。世祖遣中书侍郎李敞告祭焉，刊祝文于室之壁而还。
这应该是北魏时期很有影响的一次访祖祭祖事件。《魏书·礼志》不仅记载了这一事件，还全文收录了刊文内容，证明当时的北魏统治阶层已认可了这一遗址的可信性与重要价值。非常幸运的是，在当代中国考古工作者们的辛勤努力下，1980年，“鲜卑石室”——嘎仙洞被意外发现，它深藏在内蒙古呼伦贝尔盟境内大兴安岭东侧靠近顶巅的丛山密林之中，这一发现引起了学术界的强烈关注。据所发现的洞内题壁文字的内容，与《魏书·礼志》所记完全相符，充分证实了《魏书·乌洛侯传》关于太平真君四年（443年）北魏大臣李敞前往石室致祭记载的可信性，同时证明嘎仙洞所在方位与拓跋鲜卑口耳相传的大鲜卑山的方位大体相符，因此，将这一带作为拓跋鲜卑发祥地以及早期南迁的出发地，应该是没有太大问题的。
根据《魏书·序纪》记载，拓跋族先世部落至毛为酋长时，开始崛起。“远近所推，统国三十六，大姓九十九，威振北方，莫不率服。”因为拓跋鲜卑人的祖先“不交南夏”，我们无法在汉文史籍里找到其先祖的踪迹，因此，对于这些所谓“功绩”也无从查考。
拓跋鲜卑第一次南迁，发生在拓跋推寅（宣帝）任首领时期，其部落从“大鲜卑山”（即大兴安岭北段）进入“大泽”地区。“南迁大泽，方千余里，厥土昏冥沮洳。”显然，这里的“大泽”应为面积广大的“水草交厝”的沼泽地带。在今天的松花江及嫩江流域依然存在大面积沼泽地带，在时间较早的古代，这些地区的沼泽地面积应更广阔一些。笔者推定：嘎仙洞在今大兴安岭北段东麓，拓跋氏先民从这一带直接走下山，沿难水（即今嫩江）的支干流而南下至沼泽地区。
“大泽”的自然环境显然是不利于拓跋部落的发展的，于是，在拓跋诘汾为部落首领时，进行了第二次大规模的迁移：
献帝（诘汾父）命南移，山谷高深，九难八阻，于是欲止。有神兽，其形似马，其声类牛，先行导引，历年乃出。始居匈奴之故地。其迁徙策略，多出于宣、献二帝，故人并号曰“推寅”，盖俗云“钻研”之义。
很显然，这场迁徙运动是极为艰辛的，“山谷高深，九难八阻”，在生产力极为原始的时代，迁徙之路风险极大，困难重重。从“推寅（钻研）”之名号来看，拓跋鲜卑的首领们的确是在迁徙问题上有过相当深刻的思索与艰难的抉择。
早期大迁徙的目的地是“匈奴之故地”，“匈奴之故地”即指匈奴强盛时统辖的地盘，也就是“大漠南北”，相当于今天以蒙古高原为中心的广袤地域。
在南北匈奴分裂以及北匈奴单于遁逃之后，大批匈奴部众进入了鲜卑族控制地区，成为鲜卑族大联盟的一部分。而拓跋鲜卑可谓是与匈奴族关系最为密切的一支鲜卑族群。如关于“拓跋（托跋）”之名的来历，古史中有不同的说法，如《魏书·序纪》云：“黄帝以土德王，北俗谓土为托，谓后为跋，故以为氏。”这种说法未免过于疏阔了。“秃发”是“拓跋”二字的同名异译。《晋书·秃发乌孤载记》称：“初，（秃发）寿阗之在孕，母胡掖氏因寝而产于被中，鲜卑谓被为‘秃发’，因而氏焉。”这种解释显得过于牵强。“拓跋”二字的另一个异译是“铁弗”，《魏书·铁弗刘虎传》称：“北人谓胡父鲜卑母为‘铁弗’，因以为号。”比较而言，还是《刘虎传》的诠释最具说服力。因此，著名学者马长寿先生总结道：“……它（指拓跋鲜卑）的原始分布地在黑龙江上游的额尔古纳河流域。当匈奴西迁以后，他们向草原的中部、西部、南部迁徙，在各地不断与匈奴残余部众融合，于是始有‘拓跋’之名。”
古代鲜卑族的杰出领袖檀石槐在位期间，是鲜卑族发展史上的一段极为辉煌的时期，他对鲜卑部落大联盟实行分部而治，这种分部制度明确地记载于汉文书籍中，可见其影响相当深远，在以后相当长的时间里，这种划分应相对稳定。“自檀石槐死后，诸大人遂世相袭也。”世袭的部落大人统辖的地盘大致也会相对固定地传承。那么，拓跋鲜卑当时所在方位又是哪里呢。拓跋力微为诘汾之子，被推为“始祖”，可见其对该族发展影响之巨大。查《魏书·序纪》载云：
先是，西部内侵，国民离散，依于没鹿回部大人窦宾……后与宾攻西部，军败……始祖（指力微）请率所部北居长川，宾乃敬从。积十数岁，德化大洽，诸旧部民，咸来归附。
作为地域概念，鲜卑大联盟的“东部”与“西部”不会随意变更。这段文献中重复出现的“西部”，应为檀石槐联盟中“西部”的继续。力微既然与“西部”作战，那么，拓跋鲜卑部落当时必处于中部或东部，当然更有可能位于东部，因为在檀石槐死后，中部已为东西部交争之地。进入“匈奴故地”后，拓跋鲜卑部落最早明确的居留地为“长川”，按胡三省注：“长川在御夷镇西北，大漠之东垂也。”御夷镇城在今河北省赤城县北，长川当在蒙古大草原的东部边缘。“长川”的方位进一步证实了拓跋鲜卑当时处于蒙古高原之东部边缘地带。力微“北居长川”，证明拓跋鲜卑在两次大迁徙之后，仍在移动。
力微死后，拓跋鲜卑部落陷于混乱纷争之中，至禄官即位后，“分国为三部：帝（即禄官）自以一部居东，在上谷（今河北怀来县东南）北，濡源之西，东接宇文部；以文帝之长子桓皇帝讳猗竾统一部，居代郡之参合陂（今内蒙古凉城县东北岱海）北；以桓帝之弟穆皇帝猗卢统一部，居定襄之北盛乐故城（今内蒙古和林格尔县西北）。”而此时，拓跋鲜卑族人口数量也有了较大幅度的增长。“自始祖以来，与晋和好，百姓乂安，财畜富实，控弦骑士四十余万。”
至猗卢在位时，拓跋鲜卑重新统一起来，其控制区也进一步向南扩展。刘琨为答谢拓跋猗卢的援助，表请晋怀帝封猗卢为“代公”。而猗卢以封邑遥远为由，强行进入雁北地区。由此，拓跋鲜卑居留地整体从塞外向南移入塞内雁北地区。这是在拓跋族发展史上影响深远的迁徙运动。
帝以封邑去国悬远，民不相接，乃从（刘）琨求句注、陉北之地。琨自以託附，闻之大喜，乃徙马邑、阴馆、楼烦、繁畤、崞五县之民于陉南，更立城邑，尽献其地，东接代郡，西连西河、朔方，方数百里。帝乃徙十万家以充之。
同时，拓跋鲜卑开始分为南、北两部。“（猗卢）六年（317年），城盛乐以为北都，修故平城（今山西大同市东北）以为南都。帝登平城西山，观望地势，乃更南百里，于灅水之阳黄瓜堆筑新平城，晋人谓之小平城，使长子六修镇之，统领南部。”可以看出，当时拓跋鲜卑南、北两部正是以长城一线为分界线的。
北魏王朝的前身是拓跋鲜卑所创立的代国。拓跋什翼犍是代国的缔造者，他于338年即位于繁畤（今山西浑源县西南）之北，自立为代王。关于拓跋氏代国的疆域，文献记载相当模糊，如《魏书·序纪》云：“东自濊貊，西及破洛那，莫不款附。”
北魏疆域示意图
北魏代都畿甸示意图
代国的建立，对于拓跋鲜卑的发展具有非常重要的意义，也是拓跋鲜南迁及汉化过程的一个重要转折点。从此，在古文献中，所有拓跋鲜卑人被改称为“代人”。此外，代国内部民族构成已变得相当复杂。如有不少晋人也变成“代人”。在拓跋鲜卑早期南向开拓中，有不少汉族士人进入了其部落，凭借文化教育上的优势，他们在拓跋鲜卑的发展史上发挥了重要作用。这些人的示范作用会吸引更多的汉民进入到部落中来，“于是晋人附者稍众”。除汉族外，代国境内还有不少其他部族人士。如《魏书·官氏志》载云：“其诸方杂人来附者，总谓之‘乌丸’，各以多少称酋、庶长，分为南、北部，复置二部大人统摄之。时帝（拓跋什翼犍）弟孤监北部，子寔君监南部，分民而治，若古之二伯焉。”拓跋代国最终为前秦所灭。
道武帝拓跋珪是拓跋鲜卑的一位杰出领导者，他于386年在各部落大人的拥戴下，即代王位。这并不仅仅是拓跋鲜卑代国的复兴，而是北魏王朝的开始。对代都平城（在今山西大同市）的建设，是拓跋珪时代政治建设的标志性成果之一。对代都的建设是从天兴元年（398年）七月开始。“秋七月，迁都平城，始营宫室，建宗庙，立社稷。”“八月，诏有司正封畿，制郊甸，端径术，标道里，平五权，较五量，定五度。”从此，“代都”平城成为中国古都史上的一个名都，北魏定都平城的时期甚至被现代学者们称为“平城时代”。