律令国家の社会構造が変質していく中で、10世紀になると有力農民や豪族の一部で、自分たちの勢力を拡大するために武装し、戦う人々が出てきました。こうした人々は兵（つわもの）と呼ばれ、家子という一族や郎党などの従者を率いて国司に対抗し始めました。一方、畿内に成長した豪族は、朝廷の武官となり、武士（もののふ）として武芸をもって貴族に仕えるようになりました。

この2つの流れは次第に交流をはじめ、各地で一族の結びつきを元にした武士団が結成されました。関東地方は良馬を豊富に有したことから、有力な武士団が出てきました。下総では、桓武天皇の曽孫の高望王が平姓を与えられたことで始まった桓武平氏が勢力を伸ばし、桓武平氏の平将門は叔父の平国香を殺害後、常陸の国司に反抗していた豪族の藤原玄明と手を結び、939年（天慶2年）に将門の乱を起こしました。

将門は常陸の国府を襲い国印を奪い、下野・上野の国府を攻め落とし、関東の大半を征服後、自ら新皇と称しました。この乱に対し、朝廷は藤原忠文を征夷大将軍に任命し、関東へ急行させます。征夷大将軍の到着前に、平国香の子平貞盛が下野の豪族藤原秀郷の協力を得て将門を倒しました。

同時期、伊予の国司だった藤原純友も瀬戸内海の海賊を率いて反乱（純友の乱）を起こし、伊予の国府を奪い、東は淡路、西は太宰府まで攻め落としました。この動きに対し、朝廷は同じく藤原忠文を征夷大将軍に任命し派遣しますが、小野好古や清和源氏の租である源経基らによって藤原純友が倒され、東西の反乱は終息しました。この2つの乱は、年号から承平・天慶の乱と呼ばれます。

日本の東西で大反乱が起こったことで、朝廷は軍事力の低下を痛感しました。その後、武士を積極的に侍として奉仕させ、地方武士を国の兵として国衙に組織し、盗賊や反乱者を逮捕する追捕使や内乱時に兵士を統率する押領使に任命し、各地の治安維持に当たらせるようになりました。


武士の重要性が高まる中、源基経の子満仲は、摂津を拠点として摂関家に仕え、その子頼光・頼信兄弟も摂関家に近づき勢威を高めました。

こうした中、1028年（長元元年）に平一族の平忠常が上総・下総に勢力を広げ反乱を起こしました。朝廷は平直方に追討を命じましたが効果がなく、代わりに源頼信を甲斐の国司に任命してこれを討たせ、平忠常は源氏の武名を恐れ、戦わず降伏しました。

源氏はその後も勢力を拡大し、国司と争っていた陸奥の豪族安倍氏を源頼信の子頼義が陸奥守兼鎮守府将軍となり制圧に乗り出し、安倍頼時の死後は貞任・宗任が強固に抵抗しました。源頼義は子の義家とともに東国の武士を率い戦い、出羽の豪族清原氏の助けを受け安倍氏を滅ぼしました。これを前九年の役（1051〜1062）といいます。

その後、清原氏一族の内紛がおこり、清原真衡が家衡と争い、真衡の死後は家衡が母の連れ子だった藤原清衡と争っていました。陸奥守だった源義家は、藤原清衡を助け家衡と戦い、最終的に平定しました。これを後三年の役（1083〜1087）といいます。

源義家の介入は私合戦とされ朝廷から恩賞を与えられなかったものの、前九年の役・後三年の役を通じて源氏は東国武士団との主従関係を強め、武士の棟梁としての地位を盤石にしていきました。

源義家が去ったあとの奥羽地方では、陸奥の藤原清衡の支配が拡大しました。藤原清衡はその後平泉を拠点として、奥州と出羽の2国に勢力を伸ばし、摂関家とも交流し、京都の文化を移入するとともに北方との交易で独自の文化を育て、その子基衡・孫秀衡と三代に渡り奥州藤原氏の基礎を作り上げました。

このような状況から、11世紀には諸国の国衙の在庁官人の多くが武士となり、国司は次第に現地に赴任しなくなったことで諸国の文化の中心が国司の館から武士の館へ移り、地方社会の担い手は完全に武士となっていきました。