義仲を討った範頼と義経は、平家を追討すべく京を発つ。元暦元年（1184年）2月7日、摂津国一ノ谷の戦いで勝利を収め、平重衡を捕えて京に戻った[28][11]。この戦いの後、頼朝は義経を自らの代官として都に残し、義経の差配のもと畿内の武士たちの掌握を図る一方、四国に逃れた平家を追討すべく九州・四国の武士に平氏追討を求める書状を下して、土肥実平や梶原景時を山陽諸国に派遣した。平家追討祈願のため梶原景時・畠山重忠を圓教寺に登山させ、摩尼殿に祈祷結板を打つ。

6月5日の除目で、平頼盛が還任[注釈 37]、一条能保（姉または妹婿）、範頼、源広綱、平賀義信が国司となった[11][注釈 38]。8月8日に範頼を大将とする平家追討軍が鎌倉から出陣した。従わせた家人は北条義時、足利義兼、千葉常胤、三浦義澄、結城朝光、比企能員、和田義盛、天野遠景らである。頼朝は範頼に対し京への駐留を禁じており、追討軍は27日に京へ入ると29日に平家追討使の官符を賜い、9月1日には西海へと赴いた[11]。

10月6日、公文所を開き大江広元を別当に任じる。公文所は後に政所と名を改め、後の鎌倉幕府における政務と財政を司ることとなる[11]。20日には訴訟を司る問注所を開き、三善康信を執事とする[11]。この時期になると二階堂行政、平盛時ら中下級の有能な官人達が才能を発揮する場を求めて鎌倉に下向するようになり、彼らが幕府初期官僚組織を形成する。

文治元年（1185年）1月6日、西海の範頼から兵糧と船の不足、関東への帰還を望む東国武士達の不和など窮状を訴える書状が届く。頼朝は安徳天皇や建礼門院の無事のため、軍を動かさず九州の武士からくれぐれも反感を得ぬように記した書状を出し、九州の武士には、範頼に従い平家を討つことを求めた[11]。この状況をみた義経は後白河法皇に西国出陣を奏上してその許可を得ると[注釈 39]、10日に讃岐国屋島に向けて出陣し、19日の屋島の戦いで平家を海上へと追いやった。26日、九州の武士から兵糧と船を得た範頼は、周防国から豊後国へと渡る。3月24日の壇ノ浦の戦いで平家は滅亡し、平宗盛らを捕らえた。

これを受けた後白河法皇は4月26日に頭弁である藤原光雅を九条兼実の元に派遣して、頼朝を従二位に叙したいとの考えを伝えて意見を求めた。法皇の考えは従三位は摂津源氏である源頼政と同じとなってしまい、河内源氏の頼朝が（大きな武功のない頼政と同じに扱われて）無念に思うかも知れない、正三位でも平清盛が平治の乱の戦功で得た位階で（平治の乱で親兄弟を殺されて自身も配流された）頼朝が不快になるかも知れないと危惧していた。これに対して、兼実はそのようなことは頼朝は気にはかけないでしょうが、法皇が気にされるのであれば頼朝の勲功は過去に比類なきものであるため問題ないでしょうと答えた。しかし、光雅が退出した後、兼実は従二位は過分で従三位に進めた上で官職を与えて不足を補うべきであると愚痴を述べている[28]。かくして、4月27日に頼朝は平家追討の功により、従二位へ昇った[34]。
義経追放

文治元年（1185年）4月、平家追討で侍所所司として義経の補佐を務めた梶原景時から、義経を弾劾した書状が届く[注釈 40]。4月15日、頼朝は自由任官の禁止令に違反し内挙を得ずに朝廷から任官を受けた関東の武士ら[注釈 41]の任官を罵り東国への帰還を禁じる[注釈 42]が、同じく任官を受けた義経には咎めを与えなかった。ところが、景時の書状の他にも、範頼の管轄への越権行為、配下の東国武士達への勝手な処罰など義経の専横を訴える報告が入り、5月、御家人達に義経に従ってはならないという命が出された。その頃、義経は平宗盛父子を伴い相模国に凱旋する。頼朝は義経の鎌倉入りを許さず、宗盛父子のみを鎌倉に入れる。腰越に留まる義経は、許しを請う腰越状を送るが、頼朝は宗盛との面会を終えると、義経を鎌倉に入れぬまま、6月9日に宗盛父子と平重衡を伴わせ帰洛を命じる。義経は頼朝を深く恨み、「関東に於いて怨みを成すの輩は、義経に属くべき」と言い放つ。これを聞いた頼朝は、義経の所領を全て没収した[11]。ただし延慶本『平家物語』によると義経は鎌倉入りを許され頼朝と対面し、慰安されたのち鎌倉の外れで待機したとあり、また『愚管抄』にも義経は鎌倉の館に赴き、京に戻ってきた頃から頼朝に背く心を抱いたとあることから、『吾妻鏡』による上記の記述は誤伝または曲筆で実際には義経は鎌倉入りしているとする説もある。

義経が近江国で宗盛父子を斬首。重衡を自身が焼き討ちにした東大寺へ送ると、8月4日、頼朝は叔父・行家の追討を佐々木定綱に命じた。8月16日には頼朝の申し入れで義経・山名義範・大内惟義・足利義兼・小笠原遠光・安田義資が国司となっている。9月に入り京の義経の様子を探るべく梶原景季を遣わすと、義経は痩せ衰えた体で景季の前に現れ、行家追討の要請に、自身の病と行家が同じ源氏であることを理由に断った。10月、鎌倉に戻った景季からの報告を受けた頼朝は、義経と行家が通じていると断じ、義経を誅するべく家人の土佐坊昌俊を京に送る。対して義経は、頼朝追討の勅許を後白河法皇に求めた。10月17日、頼朝の命を受けた土佐坊ら六十余騎が京の義経邸を襲ったが、応戦する義経に行家が加勢して襲撃は失敗に終わる。義経は土佐坊が頼朝の命で送られたことを確かめ、頼朝追討の宣旨を再び朝廷に求め、後白河法皇は義経に宣旨を下した。なお土佐坊昌俊の派遣および襲撃は『吾妻鏡』『平家物語』に記載されているが、『玉葉』では17日深夜に頼朝郎従の武蔵国住人児玉党30余騎が中人の報告を受けて義経を襲撃するが行家が救援に駆け付けてこれを撃退したとある。