Når man ser tilbage på mere end tusinde års historie er det svært at skelne sandhed fra illusion. Der findes ikke nogen dokumentation der beviser eller understøtter teorier om fødslen af denne specielle kunst. De overtroiske historier fortæller at ninjaen stammer fra Tenguen, et skræmmende væsen der var halv mand og halv krage og som skulle have evnen til at ændre naturens love og menneskers bevidsthed.
Tættere på hvordan historien sandsynligvis udspillede sig, kan findes i skriftruller, der indikerer, at kunsten har sin baggrund fra militærfolk der flygtede fra Kina, da T´ang dynastiet faldt omkring år 900. Da de forskellige kongedømmer i Kina faldt, blev de folk der havde arbejdet for Kina som hærfører og generaler, som Okai, Cho Busho og Cho Gyokko, mænd på flugt. De søgte derfor tilflugt ovre på den anden siden af det smalle hav, på øen Japan. Deres lære fandt hurtigt interesserede lyttere og blandede sig med de indfødtes holdninger og fremgangsmåder omkring krigsførelse.
Udover kinesiske militærtaktikker kom der også den tæt beslægtede lære om kinesisk mysticisme, udviklet fra den esoteriske (hemmelige) viden fra Indien og Tibet. Kinesiske munke og åndemanere slog sig ned i skovene og hulerne ved Kii Peninsula fra omkring år 1024. De fremkom med systemer om integreret krops- og bevidsthedsudvikling, baseret på forståelse om universets opbygning og virkemåde. Dette blev optaget af de japanske Yamabushi (Krigermunke der levede i bjergene) og Sennin og Gyoja (Krigerasketer fra vildmarken), kinesiske præstemystikere som Kain Doshi, Gamon Doshi og Kasumikage Doshi, samt deres japanske disciple. Disse lærdomme blev ved med, at være en del af ninjaen, selv efter, de gik ind i den buddhistiske Mikkyo-(esoterisk lære)sekt i de senere år.
Ninjutsu blev gradvist sammensat gennem en blanding af disse kinesiske og indfødte japanske elementer (i modsætning til de fleste orientalske religioner og kampkunster, blev Ninjutsu aldrig direkte grundlagt på et specifikt tidspunkt i historien). Sammensætningen af den viden er senere blev kaldt Ninjutsu, blev i starten blot set som en utraditionel måde, at klare og opnå situationer og ting på. Hvad der senere blev en højt systematiseret metode til kamp og spionage startede som en skyggeagtig modkultur, en reaktion imod hovedstrømmen af den politiske og sociale tradition i Japan på denne tid. For eksempel blev Ninjutsu ryu´en (traditionen/skolen) fra Togakure familien ikke formaliseret indtil tre generationer efter Daisuke Togakure begyndte at udvikle den. I alliance med en klan der var blevet besejret i en række af slag imod overlegne styrker, tabte Daisuke alt, inklusive hans status som samurai og han flygtede op i bjergene sydøst for Kyoto. Han levede i Kii Peninsula, et område med store granskove og sumpe og i året 1162 mødte han krigermunken Kain Doshi, der var flygtet til Japan på grund af de store politiske og militære omvæltninger i Kina.
Her i bjerghulerne ved Iga provinsen (Mie Præfektur) studerede Daisuke med denne mystiker og lærte nye former for krigskunst og personlig udvikling, baseret på kinesiske og tibetanske ideer vedrørende universets opbygning. Daisuke lærte praktiske færdigheder om elementernes balance i kost, kamp, tanker, følelser og at bruge naturens kræfter og cyklusser til sin fordel. Han opdagede endvidere, at udover samuraiens begrænsede levevis som han aldrig havde tvivlet på før, fandtes der en helt ny måde at bruge sin bevidsthed på. Det var Daisukes efterfølgere der udviklede og forfinede disse færdigheder til Togakure ryu Ninjutsu og som blev kaldt ved navnet NINJA.
De fleste Ninjutsu ryu´s voksede op i bjergene på den midterste og sydlige del af øen Honsu, dette inklusive de to største, Iga-ryu og Koga-ryu, der ligesom Togakure ryu opererede i Iga provinsen og som var under ledelse af Momochi, Hattori og Fujibayashi klanerne. Koga ryu´en befandt sig i Koga provinsen (Shiga Præfektur) og optog 53 mindre kendte familier inklusive Mochizuki, Ukai, Nakai og mange andre der adopterede navnet Koga.
