Durant el període de guerra entre estats o Sengoku, un ronin anomenat Nanashi, que significa "sense nom", salva a un nen anomenat Kotarou i al seu gos Tobimaru en un temple abandonat. En Kotarou no té família i és perseguit per una misteriosa organització militar de Xina, pel que contracta a en Nanashi com a guardaespatlles.
En Nanashi, que ha abandonat el seu nom al costat del seu passat, ha "segellat" la seva espasa a causa d'un fet passat pel qual és turmentat en forma de malsons.
L'encarregat de perseguir a en Kotarou és un home cridat Rarou, que pertany a l'organització d'origen xinès i que està sota les ordres d'un ancià anomenat Byakuran, encara que, a diferència dels seus companys, Rarou no posseïx un concepte de "Rei" i solament busca lluitar contra el més fort.