A naginata kialakulása bizonytalan: vagy a kínai gun dao japán változata, vagy okinavai paraszti fegyver, vagy egy szamuráj csatolt kardot egy nyélre. Vannak olyan vélemények, hogy már a 12. század előtt harcos papok használják, de ez nem bizonyított.
Akárhogyan is, első hivatalos említése 1146-os forrásban olvasható. Ebben az évszázadban már egyértelműen a szamurájok fegyvere, a gyalogos harcosok (asigaruk) és papok (szóhei) használják. Népszerű fegyverként funkcionál a Genpei háborúban (1180-85), a Tairák és Minamotók összecsapásában. Hatékonyságát a lovasokkal szembeni helytállása biztosítja (bár kevesen lóról is használták). A következő részlet jól szemlélteti, hogyan használta gyakorlott harcos e páratlan fegyvert (a leírás az 1180-as udzsi-i ütközet egy epizódja):
„(Tadzsima nevű szerzetes) elhajította hosszú naginatájának hüvelyét, s egy szál magában a hídra lépett. Mialatt a Heikék serege gyilkos nyílzáport zúdított rá. Tadzsima egy csöppet sem rettent meg. A magasban szálló nyílvesszők elől lehajolt, az alacsonyan szállókat átugrotta, sebesen forgatott naginatájával pedig kettévágta azokat, amelyek egyenes röptűek voltak.”
A részlet a JK Oktatóképzés A katori fegyverei I. című jegyzetanyagából való.