文治元年（1185年）4月、平氏追討で侍所所司として義経の補佐を務めた梶原景時から、義経を弾劾した書状が届く[22]。4月15日、頼朝は内挙を得ず朝廷から任官を受けた関東の武士らに対し、任官を罵り東国への帰還を禁じるが、同じく任官を受けた義経には咎めを与えなかった。景時の書状の他にも、範頼の管轄への越権行為、配下の東国武士達への勝手な処罰など義経の専横を訴える報告が入り、5月、御家人達に義経に従ってはならないという命が出された。その頃義経は平宗盛父子を伴ない相模国に凱旋する。しかし頼朝は義経の鎌倉入りを許さず、宗盛父子のみを鎌倉に入れる。腰越に留まる義経は、許しを請う腰越状を送るが、頼朝は宗盛との面会を終えると、義経を鎌倉に入れぬまま、6月9日に宗盛父子と平重衡を伴なわせ帰洛を命じる。義経は頼朝を深く恨み、「関東に於いて怨みを成すの輩は、義経に属くべき」と言い放つ。これを聞いた頼朝は、義経の所領を全て没収した[7][23]。
義経が近江国で宗盛父子を斬首し、重衡を自身が焼き討ちにした東大寺へ送ると、8月4日、頼朝はかつて源義仲に属した叔父源行家の追討を佐々木定綱に命じた。9月に入り京の義経の様子を探るべく梶原景季を遣わすと、義経は痩せ衰えた体で景季の前に現れ、行家追討の要請を受けると、自身の病と行家が同じ源氏である事を理由に断った。10月、鎌倉に戻った景季からの報告を受けた頼朝は、義経と行家が通じていると断じ、義経を誅するべく家人の土佐坊昌俊を京に送る。対して義経は、頼朝追討の勅許を後白河法皇に求めた。10月17日、頼朝の命を受けた土佐坊ら六十余騎が京の義経邸を襲ったが、応戦する義経に行家が加勢し、襲撃は敗北に終わる。義経は土佐坊が頼朝の命で送られたことを確かめ、頼朝追討の宣旨を再び朝廷に求め、後白河法皇はその圧力に負け義経に宣旨を下した。10月24日頼朝は源氏一門や多くの御家人を集め、父義朝の菩提寺勝長寿院落成供養を行った。その日の夜、朝廷の頼朝追討宣旨に対抗し御家人達に即時上洛の命を出すが、その時鎌倉に集まっていた2098人の武士のうち、命に応じた者はわずか58人であった。頼朝は自らの出陣を決め、行家と義経を討つべく29日に鎌倉を発し、11月1日に駿河国黄瀬川に着陣した。一方の都の義経は頼朝追討の兵が集まらず、11月3日、郎党や行家と共に戦わずして京を落ちた。海路西国を目指す途上暴風雨に会い、船団は難破、一行は散り散りになり、義経は行方をくらませ、妾の静御前が吉野山で捕らえられている。
11月8日、頼朝は都へ使者を送ると、黄瀬川を発って鎌倉へ戻る。11月上旬、義経・行家と入れ替わるように京都に上った東国武士の態度は強硬で、法皇の知行国の播磨国に向かい、法皇の代官を追い出して倉庫群を封印している。11日、朝廷は頼朝の怒りに狼狽し、義経と行家を捕らえよとの院宣が諸国に下される[24]。12日、大江広元は処置を考える頼朝に対して全国への守護・地頭の設置を進言。これに賛同した頼朝は、周章する朝廷に対し強硬な態度を示して攻勢をかける[25]。
24日に北条時政は頼朝の代官として1000騎を兵を率いて入京した。頼朝の忿怒を院に告げ鎌倉側の要求を提出し、法皇との交渉に入った[26]。28日に時政は吉田経房を通じ義経らの追捕の為として「守護・地頭の全国への設置」を迫り、これを認めさせる事に成功する（文治の勅許）。これによって鎌倉の権力の全国的政権への確定が行われる事になる。12月には義経に荷担した反幕府派の貴族を解官・配流によって一掃し、公卿たちの知行国も指定する。九条兼実ら親幕府派の公卿を議奏とし、兼実を内覧（摂政・関白の職務の中の実質的な部分）に任命する申請を行い、朝廷の人事を鎌倉色に塗り替えさせる。鎌倉の政権はここに安泰を得たのであり、これは義経の捜索に比べるべくもない重要性を持った成果であった。頼朝は兼実に送った書状の中で「今度は天下の草創なり」とその重要性を示している。
文治2年（1186年）3月には頼朝追討の宣旨を下した責任者として法皇の寵愛深い摂政の藤原基通を辞任させ、代わって兼実を摂政に任命させる。4月頃から義経が京都周辺に出没している風聞が飛び交い、頼朝は貴族・院が陰で操っている事を察して憤りながらも、東北へも意識を向け奥州の藤原秀衡に「秀衡は奥六郡の主、自分は東海道の惣官である。水魚の交わりをなすべきである。都に送る馬や金は鎌倉で管領して伝送しよう」という書状を送り、探りを入れている。
同年5月12日には和泉国に潜んでいた行家を討ち取る。頼朝は捜査の実行によって義経を匿う寺院勢力に威圧を加え、彼らの行動を制限した。その間に発見された義経の腹心の郎党たちを逮捕・殺害し、院近臣と義経が通じている確証を上げる。11月、「義経を逮捕できない原因は朝廷にある。義経を匿ったり義経に同意しているものがいる」と頼朝は朝廷に強硬な申し入れを行なった。朝廷は重ねて義経追捕の院宣を出し、各寺院で逮捕の為の祈祷を大規模に行う事になった。京都に見捨てられた義経は、奥州に逃れ藤原秀衡の庇護を受ける事となった。
頼朝は、諸国から争いの訴えなどを多く受ける様になり、また平重衡に焼かれた東大寺の再建なども手がける。なお、頼朝は義経を庇護する寺社勢力の力を削ぐ為、あえて捕縛せずに潜伏地を遅れて追跡したのだ、とする説もある。
詳細は奥州合戦を参照
文治3年（1187年）10月、藤原秀衡が子の泰衡らに義経を将軍とする様に遺言して没する。翌年4月に頼朝は義経追討の院宣を院に求め、泰衡に義経を召し進せよとの宣旨が下される。屈した泰衡は文治5年（1189年）閏4月、衣川の館に住む義経を襲い、自害へと追いやった。
6月13日に義経の首が鎌倉に届けられると、頼朝は和田義盛と梶原景時に実検させる。25日に泰衡追討の宣旨を朝廷に求め、御家人を鎌倉に集めるが、勅許は下されなかった。頼朝は大庭景義を呼び、「今に勅許無し。なまじいに御家人を召し集む。これをして如何」と問うと、景義は「軍中は将軍の令を聞き、天子の詔を聞かず」と答えた。頼朝はしきりに喜び、景義に褒美を与える。
7月19日、ついに勅許を待たず、およそ1,000騎を率いて鎌倉を発して泰衡追討に向かい、奥州合戦が始まる。