義仲を滅ぼして源氏の棟梁としての主導権を獲得した頼朝の次の課題は、平氏打倒と諸国の源氏の掌握である。正月下旬に平氏追討の宣旨を得て、義経・範頼（のりより）軍は二月に一の谷（兵庫県神戸市）で平氏を破ってこれを西国に追い、翌文治（ぶんじ）元年（一一八五）二月に屋島（香川県高松市）を奇襲、三月には壇（だん）の浦（山口県下関市）の海戦で平氏一門を滅ぼした。頼朝はこの過程で、諸国源氏の掌握も同時に進めていくのである。
　一の谷での勝利からしばらくは休戦状態が続いた。この間に頼朝は、新たな局面に対応した態勢を整えている。元暦元年二月十八日、頼朝は使者を派遣して洛中警固を義経に命じ、山陽道の五ヶ国（播磨・美作（みまさか）・備前（びぜん）・備中（びっちゅう）・備後（びんご））の守護を梶原景時（かじわらかげとき）と土肥実平（どいさねひら）に命じた。また、諸国の武士が平氏追討を名目として荘園年貢を押領するなどの狼藉を停止しその遂行を頼朝に命じる旨の宣旨も、同日朝廷に発令させた。一週間後の二十五日、朝廷に対して、東国と北陸道における謀反人（むほんにん）の追討を確認し、平氏追討使に義経を任命し、畿内近国の武士を義経の支配下に置くことなどを要求した。次いで三月一日には、頼朝に従って平氏追討の協力を要請する下文（くだしぶみ）を九州・四国の武士に出している。同二十日に、今度は伊賀国の守護を大内惟義（おおうちこれよし）に命じている。
　この一連の政策は、諸地域における頼朝の支配権の質を背景にうちだされたと考えられる。第一に、東海・東山両道における頼朝の知行権（ちぎょうけん）と同質の支配権が、義仲滅亡によって北陸道に実現した。第二に、平氏を西国に追うことで勢力下に置いた地域の内、京都を中心とし近江国を含む畿内近国は義経に武士の統率権を委ねた。これはおそらく、平宗盛が任命された五畿内及び近江・伊賀・伊勢・丹波九ヶ国惣管職にならったものと思われる。また、山陽道や伊賀国などいまだ平氏勢力との戦闘が予想される地域には大内氏らの武将を派遣している。彼らは該当国の国衙（こくが）在庁官人に対する指揮権と軍事指揮権を併せもっていたと考えられ、のちのいわゆる守護とは異なり国レベルの追討使であろう。とはいえ、このような国内の武士を統轄する国単位の権限は、「国地頭（くにじとう）」「家人奉行人（けにんぶぎょうにん）」「国惣追捕使（くにそうついぶし）」などの曲折を経て、建久（けんきゅう）年間以後の「守護」に結実するのである。第三に、平氏の勢力下にある九州・四国地域に対しては、平氏軍に編成されている武士の懐柔策が図られている。
　こうして着々と平氏包囲網を整備する一方で、頼朝は独自の勢力を保とうとする源氏を排除していった。同年四月、源義仲の遺児義高（よしたか）を殺害、翌月義仲・義高派の残党を甲斐・信濃・伊勢で鎮圧した。そして六月には甲斐源氏嫡流の一条忠頼（ただより）、七月には信濃源氏の井上光盛（みつもり）を襲って殺している。いずれも謀反の疑いありとの理由からである。他方このような情勢から、いちはやく関東に伺候した石河義賢（いしかわよしかた）のような源氏もいた。翌文治（ぶんじ）元年（一一八五）になると、頼朝と義経の関係は急速に悪化し、六月には義経派と目された多田行綱を「勘当（かんどう）」した。十月、義経と行家に対して頼朝追討の院宣が出されたが、畿内近国の武士で義経に従う者はなく、近江武士の場合は院宣そのものを疑って国元に帰って様子を伺う姿勢をとった。十一月、今度は頼朝が義経・行家追討の院宣を得て両者の探索を開始するにいたった。そして二十九日に日本国総追捕使・同総地頭職に任じられることにより、頼朝は全国の軍事指揮権を委ねられ、武士階級を統轄する権限を獲得したのである。