Himura Kenshin [Takeru Satoh] is a political assassin who fights as part of the revolution aiming to topple the Tokugawa shogunate during the Bakumatsu in Kyoto. He joins the Chōshū clan and soon works for their leader, Katsura Kogorō, as an assassin alongside I'izuka [Shima Onishi], the examiner of executions. During one of the actions, a member of the Kyoto Watch wounds Himura in his final moments, leaving him puzzled and unsettled.
One evening, while out for a drink, he steps in to intervene with supposed members of the revolution who demand to be treated as heroes by a woman named Yukishiro Tomoe [Kasumi Arimura]. He is attacked by an unknown assassin but manages to slay him. In the aftermath, Himura finds Tomoe watching him and brings her back to his hideout, an inn used by the Chōshū revolutionaries. The next morning, Tomoe decides to stay and work at the inn. Kenshin is initially taken aback, especially as she questions and challenges his philosophy about whom he chooses to kill.
When Katsura learns of Kenshin's new relationship, he questions Tomoe's influence on him. During the Ikedaya incident (1864), an armed clash between the Ishin Shishi—comprising masterless samurai seconded by the Chōshū and Tosa clans—and the Bakufu's Shinsengumi, Kenshin rushes to the Ikedaya Inn to protect the Choshu and to rescue Katsura, but is delayed by the Shinsengumi captain Okita Sōji [Nijiro Murakami].
Before Katsura goes into hiding, he arranges for Kenshin and Tomoe to hide in the village of Otsu, outside Kyoto, asking Tomoe to look after Himura and pretend to act as husband and wife so that Himura will not be suspected. In the village, Kenshin learns to be a farmer and begins to understand what peace and happiness could mean in the new era.
Tomoe’s brother Enishi Yukishiro [Towa Araki] arrives, revealing that the two of them are spies working for the Yaminobu who are pro-shogunate and have been planning to entrap and kill Battosai the whole time. Tomoe refuses to continue with them and asks Enishi to return home to Edo, causing Enishi to lash out in anger. When Kenshin returns, he learns from Tomoe that she was once engaged to be married; however, her fiancé was killed before the wedding. Kenshin consoles her and tells her that she has done enough and that she should no longer carry the pain. As they grow closer, they share a bond as husband and wife, and Kenshin promises that he will find a way to stop killing in the new age and will protect her happiness.
The next day, Tomoe meets with the leader of the Yaminobu but is used as a pawn to weaken Kenshin. Kenshin goes to the Yaminobu to rescue her and is visibly distressed and distracted, having learned that Tomoe's fiancé was the Kyoto Watch member he had killed. Despite this emotional turmoil, he remains a capable fighter. When Tatsumi [Kazuki Kitamura], the leader of the Yaminobu, moves to kill him, Kenshin’s senses are blurred by the moment—yet Tomoe intervenes by restraining Tatsumi. Unaware that Tomoe is right in front of him, Kenshin deals a death blow, killing Tatsumi as well as fatally wounding Tomoe. Taking her last breath, Tomoe carves another scar on Kenshin's cheek with her dagger, completing the cross-shaped mark that her fiancé had begun, and she apologizes for the pain she has caused.
Shortly after, Katsura visits Kenshin at the village house to inform him that they have discovered a spy among their ranks, though Kenshin must still be prepared to join them in battle. Kenshin resolves that once the new era arrives, he will never kill again. He finishes Tomoe's diary, which explains how she evolved from seeking revenge for her fiancé to falling in love with his killer, and finally choosing to help preserve him. The film ends with the Battle of Toba–Fushimi (1868), where the Chōshū win their clash against rivals. With the Bakumatsu concluded, Kenshin faces a last challenge from Saito Hajime [Yosuke Eguchi], but he lays down his sword and vanishes into the Meiji era, leaving behind the legend of Battosai for the years to come.
