Legends around Ninja, the category of men trained for espionage and assassination, begin around the late Heian period in the mountains around Kyoto.
In the Kōga and Iga provinces, east of Lake Biwa, entire villages were established to develop this specific set of skills. Ninja were organised in three main classes:
- Jōnin - Commanded operations and made plans.
- Chūnin - Responsible for preparation and logistics.
- Genin - Who executed the plans.
According to my reference, starting in the 15th century (around the start of the Sengoku Jidai) Ninja were enlisted, mostly by Daimyo, to penetrate enemy fortifications and assassinate their enemies. So it appears that they were used less as an adjunct to conventional forces and more as a independent strike force.
In an attempt to eradicate the Ninja, Oda Nobunga sent a force of 46,000 men against Iga in 1581.
Louis Frédéric Japan Encyclopedia Harvard University Press, 2005