O nascimento do Ninja e do Ninjutsu está ligado a antigos mitos e lendas. Algumas diziam que os Ninja eram descendentes dos Tengu, pássaros demônios da mitologia japonesa. Seres alados de bico comprido, esses demônios habitavam as montanhas e acreditava-se serem eles mestres nas artes da espada e do desaparecimento.

Esses seres, representados como homens grandes e fortes, de narizes compridos semelhantes a bicos, eram ardilosos e enganadores, criando estórias para enganar as pessoas, tornando-se assim clara a semelhança que se fazia aos Ninja.

Mas, a maior parte dos historiadores acredita que os Ninja teriam surgido a partir do século VI, resultantes da sublevação de grupos políticos e religiosos.

Alguns termos relacionados ao Ninja e ao Ninjutsu fazem referência a certas habilidades e profissões. Outros não possuem uma conexão específica, somente estando ligado a um líder guerreiro que tenha se distinguido como agente ou espião. Estes termos possuem relação também com dialetos ou expressões locais, de uso único em algumas localidades.

Um ponto importante a considerarmos é que a Arte da Guerra no Japão antigo se desenvolvia de uma forma complexa e sofisticada, com determinações específicas para cada tipo de guerreiro. Após o período Nara (711-794), existiam somente poucos termos para descrever as habilidades e especialidades de um guerreiro. Mas foi por volta do século VII, que o Príncipe Shotoku usou o termo shinobi para descrever uma pessoa que lhe atendia com habilidades especiais. No caso específico do Príncipe Shotoku, este shinobi era responsável por obter informações sobre o inimigo e levar mensagens as suas tropas.

A primeira aparição Ninja remonta os finais do século VI, quando a imperatriz Suiko e o príncipe regente Shotoku Taishi os utilizaram como espiões contra um usurpador do trono chamado Morya. Homens como Mijinki no Mikoto, Otomo no Saijin e Eno Ozano foram os primeiros que puderam ser chamados de Shinobi (homens ocultos, invisíveis). O mais conhecido destes Shinobi foi Otomo Komado.

Nesta época o termo shinobi não era escrito com o kanji nin, mas era sim escrito com uma combinação de três ideogramas que formavam um só som. Tinha o significado de pessoa de grande habilidade. O uso antigo do termo shinobi, portanto pode ser anterior a introdução dos conhecimentos chineses na terminologia e filosofia da Guerra. As evidências não são claras, mas parece que o Príncipe Shotoku também se utilizava de termos como kanja para os especialistas em espionagem que possuía.

De fato, este é o termo antigo para as pessoas que se especializavam na obtenção de informações. O termo kanja vem do termo chinês kan, acrescentado ao kanji ja,que significa pessoa. Um termo similar usado, também de origem chinesa, é kancho.

O caractere cho tem o significado de olhar ao redor para obter informação, que combinado com o kanji kan produz um termo como similar a kanja. Estes termos comuns em seu uso não possuem nenhuma conexão com eventos particulares ou históricos do período. Outra derivação usando–se o kanji kan foi feita pelo imperador Tenmu que usava o termo sokkan para agentes espiões especialistas em assassinato. Existiu um guerreiro e atendente pessoal do imperador Tenmu de nome Takomi, ao qual se faz referências históricas que pode ter dado origem ao termo.