L'histoire des Yakuzas est ancienne et controversée, mais on peut aisément situer son commencement au temps des Samouraïs.
On estime qu'ils descendent des Kabuki-mono, apparus au XVIIème siècle. Le mot kabuki signifie excentrique, extravagant. L'idée d'une vie en marge de la société "honnête" était donc déjà présente. Les Kabuki-mono étaient les soldats d'élite des Shoguns, de grands chefs militaires qui dirigeaient le Japon durant l'ère Tokugawa (1600-1868). A la chute des Shoguns, lors de la Pax Tokugawa qui voit le retour progressif de l'empereur, tous les Kabuki-mono (on estimait leur nombre à environ 500 000 personnes) se retrouvent sans travail. De nombreux membres deviennent alors des bandits, pillant tout l'archipel et terrorisant les populations.
Gravure d'époque, Kabuki-mono dans son costume traditionnel.
On a toujours prêté une mauvaise réputation aux Kabuki-mono, y compris avant qu'ils ne deviennent bandits. Ces soldats étaient accusés d'arrogance, voire de cruauté. Ils avaient l'habitude de massacrer des civils pour le plaisir, et de pratiquer le Tsujigiri, consistant à tester l'efficacité d'un nouveau katana sur les passants.
Ces pratiques leurs ont valu leurs noms, car Kabuki-mono signifie tout simplement "fous".
Les Yakuzas d'aujourd'hui refusent généralement qu'on les assimile aux Kabuki-mono, en raison de leur très mauvaise réputation : ils préfèrent se désigner eux-mêmes comme descendants des Machi-Yokko ("défenseurs des villes") qui luttaient justement contre eux (mais n'en étaient pas moins aussi des bandits).
Ces Machi-Yokko comportaient deux classes distinctes : les Bakuto, qui travaillaient dans les villes, les marchés et les foires, contrôlant notamment le juteux marché des jeux de hasard, et les Tekiya qui travaillaient sur les chemins et les routes.
Mais ce n'est qu'au XVIIIème siècle que naissent vraiment les Yakuzas, membres de bandes organisées sous la houlette d'un chef. D'abord localisées dans les grands centres urbains comme Osaka ou Edo (l'ancien nom de la ville de Tokyo), elles se répandent ensuite dans tout l'archipel.
L'ère Meiji, à partir de 1868, fait entrer le Japon dans l'ère moderne. L'archipel est alors dans une intense période de changements technologiques, politiques et sociaux. Les Yakuzas s'adaptent très bien à ces bouleversements, et en profitent pour étendre leur pouvoir sur toute la société. Leurs idéaux, très conservateurs et nationalistes, les poussent à se rapprocher du monde politique et à en obtenir des avantages. Leur activité s'accroit nettement, dans une foule de domaines, dès lors qu'ils sont couverts par le gouvernement.
Quand le Japon envahit la Mandchourie chinoise, les Yakuzas, forts de leurs liens tissés avec le monde politique, en profitent pour organiser un trafic très lucratif de matériaux. Cet épisode leur permet de gagner des fortunes colossales.
Les Yakuzas profitent ensuite de la Seconde Guerre Mondiale et du chaos généralisé pour renforcer leurs trafics (drogue, sexe, armes), y compris avec l'occupant. Cette période de grande instabilité leur permet également de s'approprier une multitude de territoires.
En 1963, le nombre de Yakuzas atteint son apogée avec un nombre estimé à 184 000 personnes, réparties dans 126 gangs. Le milieu du crime organisé compte alors plus d'effectifs que l'armée japonaise.
Le nombre élevé de Yakuzas favorise les guerres entre gangs, voulant chacun conserver son territoire. Cette situation durera jusqu'au début des années 1990, où des mesures sont enfin prises par le gouvernement : la plus célèbre est la loi "Antigang" du 1er mars 1992. Vient ensuite une loi antiblanchiment en 1993. Ces mesures coercitives entrainent une forte baisse du nombre de Yakuzas, sans pour autant anéantir le crime organisé.
Aujourd'hui, on estime que les Yakuzas comptent 41 000 membres dans l'unique archipel japonais, sans compter les filières établies aux Etats-Unis, au Mexique et en Australie.
Les conquêtes militaires japonaises de l'ère Meiji ont grandement participé au développement
et à l'enrichissement des Yakuzas.