個々の主人と従者という関係は、はるか昔の縄文時代からあったに違いない。また一時的に、多くの人々を主従関係により統率するのも、集団間の争いの際に見られただろう。武士に特有の関係ではない。しかし、鎌倉時代以来の武士は、主従制に基づく持続的な組織を作り、そこから日常の行動規範を引き出した。最後は、主従制が日本の全地域をカバーするに至った。ただ、そこには一戦闘集団だったころ以来の「限界」もあった。
武士の主従制が現れたもっとも早い例は、平将門の反乱だろう。京都の公家たちの悪夢として記憶された事件である。その前史はよく分からない。「将門記」の巻頭部分が残っていない。確かなのは、天慶２（９３９）年１１月に、将門が常陸国府を襲ったことだ。その前には武蔵国権守と足立郡司が対立し、将門は郡司に味方した。この争乱に次いで１１月に常陸国府の紛争に介入し、続いて下野、上野へと戦線が広げ、いずれも国府を制圧した。朝廷に対抗して「新皇」と自称した。東国各地の国司を任命した。朝廷から派遣された押領使平貞盛、藤原秀郷に鎮圧された。押領使の子孫が関東で武士として栄えた。
将門の軍団は「従類」と「伴類」で構成されていた。「従類」は軍団の中核の騎兵、「伴類」は季節、戦況次第で増減する歩兵である。将門と「従類」の間にはゆるやかな主従関係が成立していたようだが、「伴類」との関係は不安定だった。将門の最後は、天慶３（９４０）年２月だった。春の農作業を控えて諸国から動員した兵（「伴類」だろう）を自宅に帰したスキを突かれた。元々４０００人いた兵が、最後は１０００人以下だったという。
約１００年後、平忠常の反乱が起きた。万寿５（１０２８）年６月に平忠常が安房守平惟忠を焼き殺し、さらに長元３（１０３０）年３月に上総国府を占領した。受領に対する現地勢力の反発だったらしい。しかし、忠常は中央から追討軍が派遣されると、７月には２０～３０人の随兵とともに上総・安房の国境の山に籠ってしまう。追討使の平直方は合戦をしないまま時を過ごしていたため、同年９月に罷免されてしまう。
新追討使は源頼信である。八幡太郎義家の祖父にあたる。頼信の使者が忠常の子息を伴って忠常を訪ねると、長元５（１０３２）年４月に忠常は降伏してしまう。しかも頼信を甲斐に訪ね、「名簿奉呈」（臣下になる手続き）までしたという。こうした行動の意味が分からない。忠常は４年間「反逆」を続けた。その間、２０～３０人の随兵はいたらしい。しかし、将門の「従類」との質の違いは見いだせない。組織なっていたのかも不明だ。
さらに５０年後、永保３（１０８３）年に後三年の役が始まる。陸奥守源義家が現地の清原氏の内紛に際し、一方に味方して紛争を終わらせた。口で言うと簡単だが、戦いは困難をきわめ、弟の新羅三郎義光も駆けつけ、義家はやっと勝った。終了が寛治１（１０８７）年だから、足掛け７年の長期戦だった。朝廷からは「陸奥守の業務外」と見なされ恩賞は出なかった。義家の軍団の主力は現地の兵士だった。義光と共に、義家の家人も加わったはずだが、この合戦の過程で東国武士の家人が増えたという話はない。
主従制という点では、続く寛治５（１０９１）年の事件のほうが意味は大きい。義家と弟の義綱（賀茂次郎）の家人同士が領地争いを始めたため、主人の義家と義綱が京都で合戦寸前まで行った。二人の関係は元々良好だった。しかし、家人の所領は裁判などで権利を確定する以前に、争いが起これば主人が守る。正しいかどうかを問わず、保護するのが主人の義務だ。この事件は白河上皇が義家の家人の上洛を停止したため、大事に至らなかった。同時に白河上皇は義家への武士の荘園寄進を禁止している。
さらに１００年後。吾妻鏡にこんな話がでている。文治５（１１８９）年６月、頼朝が奥州合戦のため戦の勅許を申請したが、返事が来ない。出陣を迷う頼朝が、宿老の大庭景能に尋ねた。景能がすぐに答えた。「軍中将軍の令を聞き、天子の詔を聞かず」。主従関係は天皇の言葉より重いというのだ。この言葉自体は司馬遷の史記（世家第２７）にあるのだが、武士の間では常識だったらしい。これが主従制の核心である。
元々、武士は朝廷をはじめとする権門に対しては弱者だった。さまざまな合戦のときだけ動員されて、戦力として利用されてきた。荘官の地位も、本所の決定に対して抵抗しようがなかった。そこで武家棟梁のもとに結集したのだ。初めは自己防衛という側面があった。ただ、武士団の中に対立が起きると、外部に敵を見出して合戦に持ち込み、分裂を回避する統治テクニックも見られてくる。こうした好戦的な面があるのは否定できない。
中世の武士はきわめて勘定高い。恩賞がないと思えば動かない。公家の北畠親房に「商人みたい」とけなされもした。だが命を懸けて戦うのであり、無償の奉仕は初めから眼中にない。それを前提にして、主従関係が築かれた。主と従は当然、双務関係になる。