Οι πρώτοι νίντζα ήταν στρατιώτες της δυναστείας Τανγκ όπου μετά από μία στρατιωτική ήττα κατέφυγαν στην Ιαπωνία στις σπηλιές Σάντα της περιοχής Ίγκα και Κόνγκα. Ένας μύθος λέει ότι διέφυγε μόνο ο στρατηγός Γι Γκού με μερικούς σωματοφύλακές του. Ο Γι Γκού ήταν γνώστης της τέχνης Χίτσο Όνγκνο-Τζουτσού (μία μέθοδος όπου υπερβαίνει τις ανθρώπινες δυνατότητες όπως να εξαφανίζεται από το οπτικό πεδίο του αντιπάλου με αποτέλεσμα την εξουδετέρωση του). Μια άλλη εκδοχή λέει ότι ο στρατηγός λέγονταν Cho Busho και κατέφυγε από την Κίνα στην Ιαπωνία μαζί με την πριγκίπισσα στρατηγό Cho Gyokko όπου και εγκαταστάθηκαν στην περιοχή Ίγκα και Κόνγκα που ήταν μακριά από πολιτισμό.

Στα βουνά της Ίγκα και Κόνγκα οι νέοι κάτοικοι επιδόθηκαν στον διαλογισμό ζεν και αναμείχθηκαν με τις αντιλήψεις και τις μεθόδους των ντόπιων. Έτσι οι κινέζικες στρατιωτικές τακτικές μάχης και διδασκαλίες οι οποίες ήταν μετεξέλιξη της εσωτερικής γνώσης της Ινδίας και του Θιβέτ άρχισαν να διδάσκονται στους Ιάπωνες στους ντόπιούς, και στους μοναχούς Γιαμαμπούσι (ιερείς πολεμιστές που ζούσαν στα βουνά).

Μερικοί από τους Ninja διέφυγαν πριν την εισβολή σε άλλες επαρχίες οπού και έκρυψαν την ταυτότητα τους για να επιβιώσουν.
Ένας Ταοϊστής ασκητής ονόματι Κασούμι-Γκακουρέ (αυτός που κρύβεται στην ομίχλη, ήταν Γιαμαμπούσι – πολεμιστής μοναχός ) έσωσε έναν 16άχρονο Ninja από την μάχη τον Κανεσάντα όπου τον δέχτηκε και ως μαθητή του και του δίδαξε μαχητικές τεχνικές του Ninjutsu.

Ο Κανεσάντα αργότερα άλλαξε το όνομα του σε Τογκάκουρε Νταϊσούκε όπου και ίδρυσε το νέο στυλ του Ninjutsu με ονομασία Τογκάκουρε Ρίου.Ο Νταϊσούκε Τογκάκουρε δίδασκε της μαχητικές τεχνικές, πρακτικές εφαρμογές της ισορροπίας στην διατροφή, και το πώς να χρησιμοποιείς τις δυνάμεις της φύσης προς όφελος σου. Έτσι οι απόγονοι του Νταϊσούκε εξέλιξαν και πρόσθεσαν ιδέες στην Τογκάκουρε Ρίου του Ninjutsu όπου κατέληξαν να αποκαλούνται Shinobi no mono (ειδικοί στην πληροφορία η κατασκοπεία) και αργότερα ονομάστηκαν Ninja, που ήταν άριστα εκπαιδευμένοι στην μεταμφίεση, στην αθόρυβη μετακίνηση, στην κατασκοπεία, και σκληραγωγημένοι στο σώμα αντιμετώπιζαν τις κακουχίες με ψυχή, πίστευαν στα ιδανικά και στις ανθρώπινες αξίες όπως δικαιοσύνη, ειλικρίνεια, τιμιότητα και την αγνότητα της καρδιάς.Εκτός ότι εκπαιδεύονταν στις πολεμικές τακτικές εκπαίδευαν και το πνεύμα τους σε τέτοιο βαθμό που υπερέβαινε τα ανθρώπινα όρια προφέροντας κάποιες Βουδιστικές προσευχές (Kuji Kiri) αποκτώντας ένστικτα και δυνάμεις όμοια με αυτές των ζώων.

Η μυστικότητα που ακολουθούσαν σε όλη τους την ζωή διατηρώντας διπλή ταυτότητα ήταν το πλεονέκτημα τους στις αποστολές τους. Η διαρροή μυστικών πληροφοριών μπορούσε να οδηγήσει στην ομαδική εκτέλεση όλης της ομάδας που τιμωρούνταν με θάνατο η πράξη της προδοσίας.
Η πειθαρχεία ο σεβασμός και η συνεργασία μεταξύ τους ήταν παραδειγματική.
Οι Ninja εκπαιδεύονταν στις πολεμικές τέχνες σε τεχνικές εξάρθρωσης και σπάσιμο των οστών, τεχνικές ρίψεων, τεχνικές αφοπλισμών και ακινητοποίησης του αντιπάλου.
Για να γίνει κάποιος Ninja έπρεπε να έχει γεννηθεί από οικογένεια Ninja και να εκπαιδευτεί στην τέχνη του Ninjutsu που ήταν επάγγελμα γι’ αυτούς εκείνη την εποχή.
Η εκπαίδευση τους γίνονταν και σε ομαδικό επίπεδο αλλά και ατομικό, και σε κλίμα διασκέδασης και γέλιου ήταν επίπονη και σκληρή, και είχε 3 στάδια εκπαίδευσης, του σώματος, του μυαλού και του πνεύματος, ξεκίναγε από την ηλικία των 5 ετών o μικρός Ninja μάθαινε ανατομία του σώματος και τα ευαίσθητα σημεία του, να σκαρφαλώνει σε τοίχους και δέντρα, χειρισμό ξύλινων ραβδιών (Jo, Hambo, Bo) διάφορα δεσίματα με σχοινιά, να στήνουν παγίδες, να περπατάνε αθόρυβα και να εξοικειώνονται με την αίσθηση του θανάτου.
Οι γυναίκες μάθαιναν χορό, τραγούδι, μουσικά όργανα, καλή συμπεριφορά, και προσπαθούσαν να μάθουν να φροντίζουν τον εαυτό τους και το σώμα τους για να το διατηρούν όμορφο και ποθητό για έναν άντρα ώστε να κάνουν την δουλειά τους την ώρα της ευχαρίστησης, να αποσπάσουν πληροφορίες, η να σκοτώσουν το θύμα τους με διάφορα δηλητήρια και μικρά εγχειρίδια, αυτές οι γυναίκες λέγονταν Kunoichi.

Ένας Ninja έπρεπε να μπορεί να μάχεται με πολλούς αντιπάλους ταυτόχρονα και στις αποστολές τους ήταν πολύ λεπτομερείς και προσπαθούσαν να σκεφτούν και την παραμικρή λεπτομέρεια και θα έπρεπε να διαθέτουν 6 στοιχεία υπομονή, ισορροπία, δύναμη, αντοχή, ευκινησία, και ταχύτητα.
Πολλοί Ninja είχαν πέσει στα χέρια των πολεμιστών σαμουράι που ήταν φύλακες των ανακτόρων αλλά και των σογκούν (στρατηγών) και είχαν άδοξο τέλος πριν καν προλάβουν να εκτελέσουν την αποστολή τους.
Οι σαμουράι ήταν Ιάπωνες πολεμιστές που χρησιμοποιούσαν όπλα όπως το σπαθί Κατάνα, λόγχες, τόξα, και ζούσαν σύμφωνα με τον κώδικα τιμής του Μπουσίντο που ήταν η πίστη, ο σεβασμός, αυτοπειθαρχία, η τιμιότητα και η πλήρης αφοσίωση στον αφέντη τους.

Η παράβαση σε αυτούς τους κανόνες ήταν η τελετουργική αυτοκτονία σεπούκου (χαρακίρι κόψιμο της κοιλιάς τους). Η εκπαίδευση των σαμουράι διέφερε πολύ από αυτήν των Ninja διότι γίνονταν με απόλυτη αυστηρότητα και σεβασμό και ήταν ιδιαίτερα σκληρή και συγκεκριμένη. Μάθαιναν ομαδικές τακτικές μάχης, όπλα, πολεμικές τέχνες, ιππασία, και προσπαθούσαν να κρατούν και να διατηρούν το σώμα τους γυμνασμένο και δυνατό και δεν ασχολούνταν με καμία άλλη ασχολία έκτος από την εκπαίδευσή τους.
Οι Ninja γνώριζαν ότι ο νικητής σε μια μάχη με τους σαμουράι ήταν αυτός που θα κέρδιζε τον αιφνιδιασμό και έτσι πορεύονταν μέχρι που έγιναν ο φόβος και ο τρόμος των σαμουράι.
Μπορούσαν να εμφανιστούν από το πουθενά και χρησιμοποιώντας ανορθόδοξες τακτικές και μεθόδους αλλά και όπλα και μπορούσαν να μάχονται εξ’ αποστάσεως όπως σούρικεν (ιπτάμενες λεπίδες), δηλητηριώδης βελόνες από φυσοκάλαμο και δεν είχαν κώδικες ενός ευγενούς πολεμιστή όπως οι σαμουράι τον κώδικα του «Μπουσίντο» γιατί το μόνο που τους ενδιέφερε ήταν η επίτευξη του στόχου και το πέρας της αποστολής με οποιοδήποτε μέσο και τρόπο.