雖然藤原泰衡對源賴朝採取了十分恭順的態度，但賴朝對於陸奧的野心卻並不會因此得到滿足。作為他建立全國性武士政權的最後一個阻礙，陸奧藤原氏是他必須消滅的目標。而在義經死後的1189年6月26日，陸奧藤原氏又發生了內亂，泰衡甚至出兵攻擊了一直反對自己的弟弟忠衡。看到這一情況的賴朝立刻便向朝廷要求下旨允許自己討伐藤原泰衡，但法皇這一次還是沒有允許賴朝。不過到了此時，既然賴朝早已通過任命守護和地頭的方式將全國武士都掌握在了自己手中，他也不再顧及根本無法干預武家事務的法皇，在沒有得到朝廷許可的情況下便開始集結軍隊。這支遠征軍兵源主要來自距離陸奧最近的關東地區，如果按照《吾妻鏡》的說法，其總兵力居然高達28萬人！這無疑是完全不現實的，而且要在陸奧供養這樣一支大軍也是根本不可能的，實際很可能連這個數字的五分之一都無法達到。
7月19日，完成集結的遠征軍便開始進攻了。中央的源賴朝沿東山道進軍，左翼的千葉常胤和八田知家沿太平洋沿岸推進，右翼的比企能員和宇佐美實政則位於日本海方面。8月8日，鎌倉軍與陸奧軍爆發了一場並無決定性意義的前哨戰，但兩天後陸奧軍便在阿津賀志山會戰中被擊潰。到22日，鎌倉軍已經進入了平泉，藤原泰衡則在一個月後被他的部下河田次郎刺殺，而此人後來也因背叛主人而被賴朝處死了。1190年2月，賴朝又平定了出羽方面的武士叛亂，並在同年3月任命伊澤家景為陸奧留守。至此，源賴朝已經消滅了日本國內所有反對自己的武士力量，他終於可以將精力完全集中在與朝廷周旋的方面，並將自己的政權合法化了。
雖然已經權傾天下，但源賴朝還是清醒地認識到，如果自己不能從朝廷獲得一個合適的武士官職，則鎌倉的統治便無法在自己死後繼續延續下去。如果源氏只是像平氏一樣將自己的權力寄託於朝廷體系，那麼最終還是會因受到皇室過多牽制而迅速瓦解。解決這一問題最好的辦法便是要求朝廷授予自己征夷大將軍之職，由於這一職務原本就並非律令制朝廷官位之一，而只是一個軍事任命，得到大將軍職務便等同於可以名正言順地將武士與朝廷剝離了。此外，由於將軍還擁有開設幕府的權力，只要能夠將這一職位轉變為世襲制，那麼雖然將軍在名義上仍屬於天皇的臣子，但朝廷還是將永遠失去涉足武家事務的機會。
1190年11月7日，源賴朝終於在平治之亂被放逐整整30年後首次回到了京都，而他來到這裡的目的便是希望朝廷能夠任命他為征夷大將軍，以使其能夠在法理上也成為全國武士領袖。不過後白河法皇卻只給了賴朝右近衛大將以及權大納言兩個官位。到第二年12月，賴朝仍沒有達到自己的目的。為了向朝廷施壓，賴朝在辭去了所有官位後返回鎌倉。通過這一行動，賴朝向朝廷昭示，既然現在全國所有武士幾乎都已經成為了鎌倉的家臣，自己即使無法得到征夷大將軍官位，也依然能夠以鎌倉之主的方式統御全國。如果這真的成為了現實，朝廷便將徹底失去對武士的控制力。在如此巨大的壓力下，後白河法皇卻並不准備屈服，反而進一步採取措施加強院政影響力，試圖與武士階級進行最後的決鬥。
但這一情況很快出現了翻天覆地的變化。1192年3月13日，後白河法皇駕崩了。而這位被源賴朝稱為「日本第一大天狗」的政治鬼才也帶走了皇室最後的聲望。自此之後，親鎌倉的關白九條兼實成為了朝廷的掌控者。僅僅五個月後，他便以允許原有皇室、貴族莊園土地依舊由朝廷節製為條件，將源賴朝推上了征夷大將軍的寶座，後者隨即在鎌倉開設幕府，對武士的莊園賞罰、官位晉陞則完全由幕府負責。到了此時，皇室的權威甚至已經被削弱到後鳥羽天皇立皇太子時都必須與幕府商議。皇室除在自己的皇家莊園以外，已經徹底失去了對日本的控制，新的國家體系在以幕府為核心的武家莊園制基礎上誕生了。
幕府建立後，原先的鎌倉家臣制度便被賴朝正式定為全幕府統御全日本武士的基礎。而效忠於將軍的武士則被稱為御家人，即「將軍的家臣」，並分封到了日本各地。這些御家人在平時要負擔一定的兵役、貢稅，西國御家人要在京都以三至六個月為一循環擔任警衛，東國御家人則以一至兩個月為循環擔任鎌倉警衛，幕府以這些兵役為基礎承認他們對莊園的所有權。如果發生戰爭，御家人在得到幕府命令後便應帶領一族郎黨趕往指定地點集結，並在幕府統一指揮下進行作戰，而其裝備和一部分糧食是要由自己負擔的。如果御家人在履行這些義務時有怠慢或抵觸行為，幕府便將視情況對其施以削減、沒收領地，剝奪御家人身份甚至處死的懲罰。
在普通御家人以上，追捕源義經時設立的守護和地頭則成為了幕府在各地的代理人。守護和地頭也是由御家人任命而來，相比之下，地頭統轄範圍較小，通常只是負責對某一地區的莊園進行管理，而守護要管轄一國甚至多國，因此實力要更為強大一些。這些人在平時是當地行政官員，負責追捕當地案犯，處理武士爭端，在戰時則是當地御家人的最高指揮官。不過在鎌倉早期，無論是守護還是地頭，能夠從當地稅收中所獲得的利潤都是相對較少的，他們手中的權力也要時刻受到幕府設置的西國探題、九州探題等機構監視和管轄，而且他們也並不是御家人效忠的對象，而只是幕府在各地的代理人。在賴朝成為將軍之前，這一制度原本只是鎌倉武士之間的私人主從規定。直到1185年源賴朝因追捕義經而獲得任命守護、地頭的權力之後，才逐漸成為一項正式制度，形成了一套完整的武家統治體系，保證了武家政權的長久性和穩固性。
在軍事方面，鎌倉除了將平安時代武士動員方式制度化以外並沒有做出太多改變。而武士們似乎也沒有從源平合戰中學到太多教訓，其戰鬥方式、行軍方式仍與先前無異，手中的武器也並沒有什麼變化。
就在源賴朝幾乎已經取得了完全的政治勝利之後不久，九條兼實卻被反對幕府的公卿土御門通親趕下了政壇，後者的養女又為後鳥羽天皇生下了一位皇子，後鳥羽天皇也將皇位讓給了這位皇子，尊號為土御門天皇。1199年1月，源賴朝又在一次外出中從馬背上摔下而亡。自源賴朝成為征夷大將軍僅僅七年時間，幕府便似乎面臨著土崩瓦解的危險。
繼承人源賴家對比企能員的重用也令御家人感到極為不滿。1199年4月12日，13名重臣通過合議而剝奪了源賴家的訴訟裁判權，削弱了將軍的絕對權威，此後有實力的御家人對幕府領導權的爭奪愈演愈烈。在幕府的混亂之中，1200年9月，朝廷強令幕府處罰了三位四國的守護，而幕府對此雖然百般阻撓，卻並沒有成功。
面對幕府即將崩潰的局面，源賴朝的遺孀北條政子突然站了出來，並與其父北條時政一同迫使不得人心的兒子源賴家交出幕府控制權，並剷除了自賴朝時代便作為源氏親信存在的梶原景時。1203年8月，北條氏以源賴家生病為由迫使其退位，政子的另一個兒子源實朝成為將軍，北條時政以執權的頭銜統轄幕府。不久之後，比企能員一族也被北條氏屠殺。1204年7月18日，源賴家也被暗殺，北條氏在幕府內部確立了統治性地位。造成這一結果的根源，則正是源賴朝起兵反對平氏時，對於北條時政的依賴。
北條時政在1215年死後，其子北條義時仍在擴張北條氏的權勢，源實朝在對將軍權力絕望之餘甚至希望逃往南宋。而北條義時為壓制其他御家人，又試圖將守護的終身制也改為交替制，最終因所受阻力過大而沒能實現。1213年，御家人之間終於爆發了反對北條氏的暴亂，但暴亂的結果非但沒有讓北條氏的權力受到削弱，卻終於使北條氏得以剷除反對勢力，並將執權一職世襲化。
1219年1月27日，源實朝在被朝廷封為右大臣當天遭到刺殺。由於沒有直系子嗣能夠繼位，北條氏最後只能在旁系血親中選擇攝關家的左大臣九條道家之子，年僅兩歲的藤原賴經繼承源氏宗家，但此人直到1226年才被授予將軍頭銜。在那之前，幕府的權力事實上被掌握在了早在源賴朝死後便出家成為尼姑的北條政子手中，後者也因此得名「尼將軍」。
面對幕府愈發混亂的情況，朝廷終於在1221年5月正式開始了公開的軍事倒幕行動，後鳥羽上皇試圖以北面武士、西面武士兩支近衛軍為主力，再輔以僧兵以及皇室莊園的武士來消滅北條氏，並以此作為推翻幕府的第一部。不過這位上皇卻忽略了一個事實——無論幕府內部發生了多麼嚴重的混亂和內鬥，那也只是武士內部的問題。無論如何，武士們也絕不願意重新回到皇室和公卿總攬大權、武士只能作為其走狗的時代。在北條政子的鼓動下，就連皇室莊園的莊園主都紛紛投靠幕府，使幕府軍人數達到了19萬人之多（《吾妻鏡》數字，明顯有著誇大成分），而朝廷卻只能集結起大約2萬人。短短一個月後，幕府軍便在6月15日攻入京都，朝廷被徹底肢解。自此