武蔵に入った頼朝は、江戸重長には格別な配慮を示し、『吾妻鏡』治承四年（一一八〇）十月五日条によると「武蔵国諸雑事など、在庁官人ならびに諸郡司らに仰せて沙汰致さしむべきの旨」を重長に命じており、このことは重長を武蔵国総検校職に任じたことを示している。この武蔵国総検校職は、後述のように本来秩父一族の惣領家の補任職であったのに、兄筋の畠山重忠や河越重頼をさしおいて頼朝が重長を任命したことは、彼が「八か国の大福長者」（源平盛衰記）「重能・有重折節在京、武蔵国において、当時汝すでに棟梁たり」（『吾妻鏡』治承四年九月二十八日条）と言われた実力によるものであった。
続いて頼朝は、十月八日に足立郡の豪族足立右馬允遠元に対して、次のように「郡郷領掌」を許している。
足立右馬允遠元、日ごろは労あるの上、最前召に応じ、参上の間、郡郷を領掌する事、違失有るべからざるの旨、仰せらる云々（『吾妻鏡』治承四年十月八日条）
右の「郡郷領掌」の具体的内容は明らかでないが、先の十月五日の吾妻鏡の記述に頼朝が武蔵支配に当って、在庁官人、郡司等従来の国衙機構を通じて行なうと述べているので、当時足立郡きっての有力者で郡司でもあり、かつ父義朝以来源氏に心を寄せていた足立氏の、郡機構の支配権とその本領を安堵したものと思われる。
こうして南関東の支配を固めていった頼朝に対し、西から平氏の軍事的脅威が加わってきた。頼朝挙兵の急報が京に伝えられたのは九月初旬で、中央貴族の中には、かつての平将門の乱を想起する者もあった（『玉葉』）。かような緊急事態に対し、平清盛は、子息維盛を総大将として頼朝追討の軍勢を派遣したが、途中源氏に心を寄せる地方武士の反対にあって、糧食調達や兵士徴発もうまくいかず、もはや昔日の勢威は見られなかった。このため全軍の士気は落ち、富士川で頼朝軍と対した際、水鳥の羽音に驚き、戦わずして敗走した。
この時頼朝は平氏の軍を追撃して一挙に福原を突こうとしたが、千葉常胤・上総介広常等挙兵以来の功労者の反対にあい、ひとまず鎌倉にもどって遠江以東を自己の軍事的支配圏にする体制固めに専念することとなった。そして十一月、頼朝は反転して奥州藤原氏と共に頼朝の背後をおびやかしていた常陸の佐竹氏討伐を行い、下河辺庄司行平や熊谷直実、平山季重らの活躍によって帰服させ、佐竹氏の旧領を戦功の士に宛行い鎌倉に帰った。
この年十二月十二日には、鎌倉大倉郷に待望の宿館も完成し、新亭移徙の式が執行された。侍所には三一二人の有力御家人が出仕した。『吾妻鏡』には、これより以降、東国の御家人達は皆頼朝の行動が道理にかなったものとして「鎌倉の主」（鎌倉殿）として推戴したと述べており、頼朝を中心とした東国政権はこの時点に確固たる地位を築いていたことを示している。そこで頼朝は臣従する御家人に対し、本領安堵・新恩給与を行う義務を生じた。これより先、富士川合戦に勝利をおさめた直後の治承四年十月二十三日には相模の国府で初めて御家人に勲功行賞を行い、北条時政をはじめ千葉常胤・上総介広常・安達盛長ら有力御家人に、或いは本領を安堵し、或いは新恩を与え、下河辺行平には、元の如く下河辺庄司たることを許している。ここに、従来の公権力や、荘園領主の権限を越えて頼朝の在地支配権が行使され、東国武士には頼朝が最高支配者として写ったのである。
次いで同年十二月十四日、さらに広範囲に本領安堵を実施し、武蔵国の住人に対して、次のように所領所職の安堵を行なった（『吾妻鏡』治承四年十二月十四日条）。
武蔵国の住人、多く本知行地主職を以て、本の如く執行すべきの由、下知を蒙むる、北条殿并びに土肥次郎実平奉行と為る、邦通之（これ）を書下すと云云
この本知行地主職とは、武蔵国の住人が先祖相伝の土地として所有してきた名主職のことで、頼朝の家人として名簿を捧呈し、或いは見参を許されていた武蔵武士が本領を安堵され、或いは新恩の給知を受けて、秩父氏のような有力大豪族層から名主的小地主層に至るまで、鎌倉殿との結びつきを一層強固にしたのである。こうして頼朝と東国武士との間には土地を媒介とする強固な主従関係が成立し、具体的には「御恩と奉公」に結ばれた新しい封建的関係が成立していたのである。
一方平清盛は、頼朝に反撃しようとしたが果さずして没し、畿内西国では興福寺等の僧兵の反平氏運動、近江源氏の挙兵、九州豪族の反抗が平氏政権を揺るがし、この機に乗じ寿永二年七月木曾義仲が源行家とともに入京した。平氏はこれを支えきれず幼帝安徳天皇を奉じて西に落ちのびた。後白河法皇は、義仲・行家に功賞を行うと共に、他方頼朝に上京を促して義仲との対立を策した。しかし頼朝は直ぐには上京せず、平氏押領の社寺権門の所領を本主に返付させるのが自分の政策であるむね上申し、この年閏十月、「東海・東山道等の庄（公）土、服せざるの輩あらば頼朝に触れて沙汰致すべし」とのいわゆる「寿永の宣旨」を得たのである。これによって東海・東山諸国の国衙領・荘園における裁判権・強制執行権・追捕権は、あげて頼朝の手に委ねられることとなり、頼朝の東国支配権が公認されることになった。このことは、鎌倉幕府の成立をここに求める説もあるように画期的な意義を持つものであった。
次いで元暦元年（一一八四）正月、範頼・義経兄弟が兄頼朝の代官として義仲を近江粟津で敗死させ入洛すると、早速法皇に迫って平氏追討の宣下を受け、一の谷に平氏を敗走させた。翌文治元年二月の屋島の戦いを経て、翌三月長門壇ノ浦に激闘半日の後、平氏一族を全滅させた。ここに頼朝挙兵以来四年半で治承・寿永の内乱は終りを告げ、頼朝の朝廷に対する軍事的政治的地位の優位性は確立し、幕府成立の基盤が固められていった。