Envoltas em lendas cheias de mitos antigos, as origens dos Ninjas baseiam-se na crença de que eles descendiam do Tengu, pássaro-demônio da mitologia japonesa. Ainda que a maioria dos historiadores aceite que o ninjutsu tenha nascido no Japão, motivado pelas agitações político-religiosas do século VI d.C, é na China que devemos buscar sua origem. Por volta de 500 a.C, um grande filósofo, general e estrategista militar chinês chamado Sun Tzu, escreveu um livro intitulado "A arte da guerra", um tratado sobre a ciência exata de temas como estratégia ofensiva, fraquezas e forças do inimigo, terreno, emprego de espionagem, operações de guerrilha e vulnerabilidade. Considerado modelo de leitura para intelectuais chineses e militares, até sacerdotes taoístas e budistas tinha conhecimento do seu conteúdo.

Embora vivesse numa era de constante violência, seu extraordinário senso de paz fazia Sun Tzu, em seu intimo, acreditar que estratégias adequadas e informações seguras sobre os planos do inimigo deviam conduzir o objetivo de uma guerra, não a concebendo como mera chacina e destruição. Sua diretriz primordial era que o estrategista habilidoso fosse capaz de subjugar o exército inimigo sem confrontá-lo, tomar suas cidades sem atacá-las e derrotar o seu estado sem derramamento de sangue. Fiel defensor da espionagem e operações secretas, ela afirmava que o uso de suas táticas daria um veloz resultado a uma guerra iminente.

Baseados nas táticas contidas nesse livro, os Ninjas desenvolveram suas técnicas características de luta. Os precursores dos Ninjas foram guerreiros que levavam uma vida mística, eremitas apartados da nascente sociedade feudal japonesa.

A primeira aparição Ninja remonta nos finais do século VI d.C, quando a Imperatriz Suiko e o Príncipe Regente Shotoko Taishi, um budista veemente, utilizaram espiões contra um usurpador do trono chamado Moriya. Homens como Mijinki No Mikoto, Otomo No Saijin e Eno Ozano foram os primeiros que puderam ser chamados de Shinobi.

Ao se tornar governante, Shotoku promoveu diversas mudanças administrativas no país e transformou o Budismo na religião oficial do Japão, sendo o próprio Xintoísmo, religião nativa, relegada a segundo plano. Com sua morte, em 622, teve início um período de guerras civis. Os conflitos terminam em 645, e a organização centralizada do estado, proposta por Shotoku, refletiu-se novamente na reforma Taika de 645, empreendida pelo imperador Kotoku. Esse por sua vez estabeleceu o mesmo sistema de governo vigente na China, onde todas as terras e a população ficariam sujeitas ao governo central, a monarquia absoluta. Todos os camponeses seriam obrigados a pagarem impostos.

Por discordarem deste novo sistema de governo e fugindo de perseguições político-religiosas impostas pelos aristocratas - esses viam a crescente influência dos budistas no governo como uma ameaça - certos seguidores do budismo Shingon, formadores do Shugendo (uma mistura de Budismo, Xintoísmo e Taoísmo), resolveram instalar-se em uma região inóspita e montanhosa do Japão (em torno das antigas províncias de Iga e Koga) e, por isso, foram então chamados de Yamabushi (Monges Guerreiros da Montanha). Esses guerreiros, que passaram a se organizar em bandos, foram os responsáveis pela formação dos primeiros Clãs Ninjas, bem como pela consolidação de uma nova arte marcial, o ninjutsu, que foi uma adaptação às necessidades da época e uma evolução do que já existia até então.