Si intentamos encontrar un único origen del Ninjutsu, pronto nos damos cuenta que cada documento con mayor o menor antigüedad tiene su propia teoría. Si tomamos como ejemplo dos de los documentos más famosos sobre Ninjutsu, en las primeras líneas del capítulo “preguntas y respuestas” (忍術問答) del Bansenshūkai (万川集海) nos dice que los orígenes se remontan a los personajes mitológicos Fuxi (伏羲) y El Emperador Amarillo (黄帝). Mientras que el Shinobi Hiden (忍秘伝), en su primer capítulo “biografía de Iga y Kōga” (伊賀甲賀伝記) dice hallar sus orígenes en Liu Bang (劉邦)*1.

Otro documento que nos hace viajar a China para encontrar las raíces del ninjutsu es la “crónica de los disturbios en Iga” (伊乱記) también conocido como “disturbios en Iga (en la época) Tenshō” (天正伊賀の乱) escrito por Kikuoka Nyogen (菊岡如幻) en el 1679. En el se dice que el origen del ninjutsu está en Oiru Tayuya (御色多由也)

Página del Iranki (伊乱記) donde nos expone su teoría de los orígenes del ninjutsu

...“Desde el amanecer hasta el mediodía, dedicaban en cuerpo y alma a Shinōkōshō (士農工商)*2. Luego, desde el mediodía hasta el anochecer, se dedicaban plenamente a perfeccionar la lucha, el arco y la equitación, además del entrenamiento de técnicas de ocultación (側隠術).

Se consideraba que, desde tiempos antiguos, el legado de Iga había sido preservado, transmitiendo los conocimientos de espionaje (chōjutsu 諜術) desde la época de Oiru tayuya (御色多由也) hasta el presente. En esa región, destacaban Tatenoka no Dōjun (楯岡の道順), Kōga Tarōbei (甲賀太郎兵衛)*3, Takayama Jirōtarō (高山次郎太郎), Kogushi (小串), Ōgushi (大串) y Kido (城戸). A través de generaciones, la región se había llenado de individuos con estas habilidades, y hasta la fecha se continuaba transmitiendo actuación como agentes de inteligencia “shinobi” (間諜「しのび」)”...

A pesar de tener un nombre japonés, los orígenes de Oiru Tayuya hay que buscarlos en China, concretamente en la historia de Xu Fu, un alquimista Chino de la dinastía Qin. El emperador Qin en su afán de alcanzar la inmortalidad envió a Xu Fu junto con una expedición de miles de personas (entre ellas recolectores de medicinas), a la búsqueda del elixir de la vida eterna. Se dice que acabó desembarcando en Japón en el área de Kumano para llegar posteriormente a Iga y transmitir (entre otros) los conocimientos del Ninjutsu. 

Se dice que, en el año 72 del emperador Kōrei (孝霊天皇), año 229 AC., un súbdito del primer emperador de China, Qin Shi Huang (始皇帝), viajó a Japón, entonces conocida como "Yakkyoku" (薬局, literalmente "farmacia"), en busca de un elixir de inmortalidad y allí introdujo el ninjutsu.

Xu Fu (徐福, Jo Fuku en japonés), acompañado de quinientos hermosos jóvenes y doncellas menores de quince años, desembarcó en la costa cerca de Shingū (新宮), en la región de Kumano (熊野). Xu Fu recorrió las montañas de la región de Kishū (紀州) buscando el elixir de la inmortalidad, pero al no encontrarlo, renunció a regresar a China y decidió establecerse allí. Mientras vivía en los bosques cercanos, Xu Fu enseñó a los japoneses diversas técnicas, como la caza de ballenas, la fabricación de papel, la creación de cuchillas para cortar huesos, e incluso el método para hacer tabaco. Además, transmitió conocimientos de ninjutsu.

Expedición de Xu Fu para encontrar la medicina de la vida eterna. Utagawa Kuniyosi (歌川国芳)

Según una versión, Xu Fu no tenía intención de establecerse permanentemente en Japón y, tras su estancia, regresó a China, dejando atrás a dos mujeres. Estas mujeres, Oiru Tayuya y Oyumichi Dayū (大弓路太夫) se trasladaron de Kishû a Iga (伊賀) y transmitieron el ninjutsu a los habitantes de Iga. Pero también se dice que Oiru Tayuya fue el nombre que Xu Fu adoptó al naturalizarse japonés. 

Koyama Ryūtarō (小山龍太郎) en una charla con Masaaki Hatsumi (良昭初見) publicada en la revista mensual de artes marciales Hidden (月刊秘伝), comenta que Takamatsu Toshitsugu (高松寿嗣) no creía que Xu Fu, fuera el primer naturalizado japonés que trajo los conocimientos que darían origen al ninjutsu japonés, sino que fue Ibō (異匄, o Ikai) quien aparece recogido en la línea de transmisión del Togakure Ryū (戸隠流). También el historidor Okuse Heishichirô (奥瀬平七郎) en su libro “Ninjutsu: su historia y el ninja” (忍術: その歴史と忍者), propone que realmente Oiru Tayuya fue referido posteriormente como Tagoya (多胡弥), un espía a las órdenes del emperador Tenmu (天武天皇, año ¿? - 686). Según el Bansenshûkai y algún otro manuscrito del estilo y época, este Tagoya es el origen del Ninjutsu en Japón.