Durante o período Edo, a filha de um mestre de artes marciais embarca numa jornada de vingança pelos pais assassinados. Para acompanhá-la, Rin escolhe como guarda-costas o imortal Manji, apelidado de Assassino de Centenas. Seu alvo é o chefe dos Ittou-ryu, Kagehisa Anotsu, o homem que ela mais odeia no mundo. Dá-se início à aventura do homem que nunca morre e da garota em busca de vingança.

Rin anuncia que irá encontrar-se com o amigo do pai, Souri, o pintor, na sua jornada por vingança. Souri não pode ajudá-la, mas lhe dá dinheiro. Com a carteira cheia e nenhuma pista, Rin encontra a espada do pai na serralharia de onde foi supostamente roubada. No entanto, a arma está na posse de um espadachim do Ittou-ryu, Taito Magatsu.

Uma prostituta se aproxima de Manji enquanto ele espera por Rin e, apesar de perceber sua artimanha, ele aceita o convite dela. A mulher, Makie Otonotachibana, parece fraca demais para ser uma guerreira do Ittou-ryu, como afirma. Depois de poupar a vida dela, ela reaparece diante de Manji com olhos e cabelos diferentes.

Buscando se fortalecer, Rin recebe treinamento de Manji, mas está longe de se equiparar a ele em habilidade, menos ainda à escola Ittou-ryu. Em melancolia, Rin é atraída por um barulho e encontra um homem treinando sozinho. "Um dia, eu serei como ele", ela pensa, mas logo se surpreende ao ver o seu rosto. É o seu arqui-inimigo, o chefe dos Ittou-ryu, Kagehisa Anotsu.

Após ver Kagehisa, Rin fica desamparada. Perdida em pensamentos, ela e seu guarda-costas Manji são abordados por um monge budista. O monge é Eiku Shizuma da Ittou-ryu. Ele luta com Manji, mas é rapidamente derrotado. No entanto, apesar do golpe letal, Shizuma se levanta e a ferida se regenera integralmente. Shizuma possui um corpo "imortal", assim como Manji.

Rin conhece uma criança atrevida, Renzou, durante o festival. Na loja de máscaras, as coisas esquentam entre Manji e Araya, e a hostilidade só se dissolve quando o filho de Araya, Renzou, aparece. Araya e Renzou deixam a loja. Tendo observado Manji de longe, Rin tem motivos para encarar Araya com olhos de choque e ódio.

Começaram as discussões sobre a tarefa de nomear o instrutor da escola Ittou-ryu, previsto pelo xogunato. A espada da Ittou-ryu deverá ser conhecida no mundo. Taito Magatsu promete tornar isso realidade, mas decide sair do lado de Kagehisa Anotsu. Paralelamente, os líderes dos Ittou-ryu se tornam alvos. A ponta dessa lâmina também está apontada para Magatsu.

Manji e Rin envolvem os quatro conhecidos como Mugai-ryu, os quais mantêm informações sobre Kagehisa, com o intuito de assassiná-lo. Deitada na estrada que deixa Edo, e com base em informações conhecidas apenas por Rin, ela e Shira se aproximam de Kagehisa enquanto ele tenta fugir dos outros.

Rin was told of Kagehisa's whereabouts by Giichi, and now her and Manji are suspected of indiscriminate murder. Suspected criminals cannot pass the checkpoint. But thanks to a maid who was acquaintance of Rin's, she has a countermeasure. She heads alone to a village that can help her slip through the checkpoint.

Manji wants to go after Rin, but he has no pass. That's when Souri and Magatsu appear before him. Souri tells Manji that he can acquire as many passes as Manji likes, but there's a condition. Meanwhile, a gray-haired, one-armed Shira appears before Hyakurin and Shinriji as they re-work their plan for assassinating Kagehisa.

Having become traveling partners for the sake of their goals, Manji and Magatsu are assaulted by a group of bald men. Manji, groaning in pain, is approached from behind by Shira, who then lops off Manji's arm. Shira had reconstructed his body, and desired a rematch with Manji. But now Magatsu, whose important woman was killed by Shira, stands in his path.

Having left for Kaga in pursuit of Kagehisa, a collapsed Rin is rescued by the very same Kagehisa. Then, having to cooperate with Kagehisa who is pursued by the Shingoto-ryu, Rin starts to see Kagehisa, her enemy, as a human being.

The Ittou-ryu had its members slaughtered by the shogunate. Kagehisa gathers the remaining members of Ittou-ryu in secrecy, and plots revenge against the shogunate. Manji is invited to the Mugai-ryu by Giichi, but he refuses, and they clash swords. Giichi's weapon breaks, so a truce is called. Manji decides to go meet the head of the Mugai-ryu, Habaki.

Habaki's scheme gets Manji trapped in a dungeon. Habaki uses a doctor, Burando Ayame, to try and solve the mystery of the immortality. For the sake of the advancement of medicine, Burando sinks a scalpel into Manji's body. Meanwhile, while waiting for Manji's return, Rin is caught up in a strange cohabitation with Doua and Isaku, who had been searching for a place to stay.

Burando succeeds in transplanting Manji's left arm onto the test body of Dewanosuke. From that starting point, more tests succeed. But Habaki puts pressure on Burando, and demands results. Habaki's blade closes in on the imperfectly immortalized Dewanosuke. Rin meets with Doua and Isaku in the street as she searches for Manji. That's when the official that Doua knocked over appreaches them.

Ever since the Dewanosuke incident, Burando kept making blunders. He is finally thrown in solitary confinement by Habaki, and goes insane. But as a result of his madness, Burando grasps something important about the immortality experiments: That humans are essentially otters. Meanwhile, Rin and Doua resolve to infiltrate Edo Castle to rescue the surrounded Manji and Isaku.

Manji and Rin finally reunite. But the formidable foe they made in Habaki in the dungeon blocks their escape. Then Doua and the presumed dead Isaku arrive as backup. The dungeon begins to cave in. As their escape nears, an unexpected person appears before Rin and Manji. Then, the answer that Burando arrived at from the results of his experiments...

After his failure at Edo Castle, Habaki is dismissed as head clerk. But still, in order to annihilate the Ittou-ryu, he heads up the Rokki-dan in hopes of subjugation. However, the new head clerk, Ugen, decides that Ittou-ryu, having left Edo, is now in the clear. Furthermore, to ensure he abides by the agreement, Habaki's wife and children are taken hostage.

Rin and Manji chase after Kagehisa, but Shira attacks them and Rin is taken away. Manji goes to rescue her, and meets not only Shinra, but Renzou as well. Manji fights Shinra in order to rescue Rin. But astoundingly, what slashes at Manji is Shira's left arm, which should have been lost.

Manji is wounded from his duel with Shinra. Renzou picks up a sword and tries to kill Manji, but Rin and the others talk him down. Meanwhile, Habaki is livid upon learning of the attack on Edo Castle. Habaki wants to pursue Ittou-ryu, even in absence of its leader. As a result, one of the Ittou-ryu enters a mountain village. Habaki's daughter, Ryou, tries to subdue him to be of use to her father.

Arashino, Hasshuu, and Murasaki of the Rokki-dan act as the vanguard in the clash with the Ittou-ryu. The crucial Abayama manages to escape with the help of his followers. But then he hast to confront Giichi and Hyakurin, who pursued Abayama to assist Habaki.

The Ittou-ryu, Rokki-dan, and Manji and Rin all gather in Nakaminato, as if guided there. They all bear their motives on their swords in the moment they begin their final deathmatch. Deceive, subdue, and dance in chaos. Sparks will fly in the decisive batte between the strongest. The last laugh belongs to...

The lives of those gathered fizzle out one after another. Those remaining are battered and bruised. Yet still they take up their swords, and slam their convictions against one another. The last one standing... And the revenge that was fulfilled... The curtain now closes on the tale of the man with an eternal life, and of those people whose finite lives were a blaze of passion.