In a soba (noodle) shop, Mizu encounters a "flesh-trader" (a purveyor of women to brothels) with a Western pistol. Mizu forces him to reveal the name of the weapons dealer, Heiji Shindo. Ringo, the kitchen attendant, follows Mizu and implores to be taken as an apprentice.

Princess Akemi, the only daughter of the Daimyo of Kyoto, Lord Daiichi Tokunobu, convinces her father to approve of her marriage to Taigen, a young and accomplished samurai. Mizu seeks a meeting with the master of the Shindo Dojo to find out the location of his brother, Heiji Shindo. When the request is denied it leads to conflict; Mizu defeats the students easily. Taigen, who tormented Mizu as a child, is now the dojo's prized champion, but when Mizu defeats him, the master reveals the location of his brother.

In a flashback as a child, Mizu encounters Master Eiji, a blind swordsmith; they recover a glowing blue metallic meteorite. She becomes his apprentice and learns swordsmithing and swordcraft.

Reluctantly allowing Ringo to join her, Mizu arrives at a coastal town, seeking to hire a boat to reach Shindo’s island fortress. Shindo and the foreigner plot a 'surprise' for the Shogun in Edo. Taigen pursues Mizu to regain his honor. Because of Taigen's defeat, Akemi's father plans to marry her off to the Shogun's widowed second son and will take her to Edo in five days, despite her objections. She decides to run away in search of Taigen, although her father's retainer Seki catches her and, unable to stop her, joins her instead.

Taigen and Ringo take Mizu to shelter at a nearby shrine. Mizu agrees to a contract to duel Taigen once she is recovered. A huge man with a club delivers an invitation to a ‘Tea ceremony’ with Heiji. Though Taigen suspects this to be a trap, Mizu accepts and they both travel to the meeting. Heiji gives Mizu three options: be paid off to renounce her vendetta, be smuggled into Heiji's castle in sake barrels to kill the white man, or refuse and be killed by archers supposedly hiding nearby. Mizu calls Heiji's bluff and cuts off his arm. Taigen and Mizu escape with Ringo's help while being bombarded by hundreds of arrows. Afterwards, Mizu knocks Taigen unconscious and leaves him with Chiaki's broken blade and a note promising to attend their duel at a later time. Taigen is subsequently kidnapped and taken to Heiji's castle.

Mizu seeks out Madame Kaji’s brothel to follow up on what Heiji Shindo revealed about how prostitutes enter the castle of Abijah Fowler, the white man she is seeking. Kaji promises to give her the information if Mizu agrees to mercy kill Kinuyo, a deaf-mute girl who was in Kaji's care before being forcibly taken by the local "thousand-claws" mob boss Hamata. After convincing Kinuyo to believe Mizu will protect her, Mizu carries out her task and leaves the scene making Kinuyo's death look like an accident. However, on her way out a boy sees her; Hamata arrives at Kaiji's brothel with his fighters and orders them to kill everyone.

After realizing Akemi has run off, Lord Daiichi sends his men after her. Akemi ends up in the same town as Mizu and sees her with Taigen's scarf, entering the brothel. Akemi persuades the purveyor to trade her there. To prove her competence when tasked by Madam Kaiji with pleasuring a veteran customer with erectile difficulties, she tactfully uses his interest in poetry and her proficiency in the subject to stimulate and bring him to climax. While she's being applauded for her talent she volunteers to serve Mizu in an attempt to drug her.

Faced with the threat of Hamata's men, Mizu gathers the women of the brothel in the cellar and tasks Ringo with guarding them. Inside the brothel, she starts taking out the thousand claws individually, but one manages to wound Mizu, resulting in her slowly losing strength.

In a flashback Mizu has while being attacked, allegorical with the tale of the first rōnin, Mizu is seen receiving a similar wound from some gangsters, and is later saved by her presumed-dead mother, who goes on to arrange a marriage between Mizu and a disgraced samurai, Mikio. Mizu gradually opens up to her new husband, but when she beats him in a sparring match, he calls her a monster. He fails to help her when soldiers arrive to collect the bounty on her head. Feeling betrayed, she battles the group and kills them. Mikio and Mizu's mother fight over who betrayed Mizu. Mikio stabs Mizu's mother to death. Mizu kills Mikio and leaves. A narrated bunraku puppet theater play intersperses and complements the storytelling, with its female protagonist eventually transforming into an Onryō, a vengeful spirit.

In reality, Mizu is pinned down but manages to summon back her strength, turns her sword into a makeshift Naginata, and kills Hamata’s men. The men sent by Lord Daichi arrive to take Akemi back home and though she pleads with Mizu to help her, Mizu doesn't intervene. Ringo, angered over his master's callous decision, ends his apprenticeship.

Mizu follows the instructions relayed by Madam Kaji, finding the underground passageway to the castle littered with the skeletons of women and infants. While trying to unlock the door to exit the tunnel, she accidentally triggers a water trap and just manages to escape drowning, but loses most of her gear. Her covert entrance is blown when a soldier sounds the alarm, interrupting Heiji and Fowler's meeting at the upper level with two of the Shogun's advisers as they conspire to kill the Shogun and his family to take power by force using guns in Fowler's possession.

Ringo saves Mizu and Taigen, bringing their unconscious bodies to Sword Father’s hut. While recovering, Mizu's relationship with Taigen starts taking a non-combative and suggestive turn. This comes undone when she reveals Akemi's marriage to the Shogun's son, and of Fowler's impending attack on the Shogunate. Taigen rejects Mizu's broken blade and leaves for Edo to save Akemi and warn the Shogun, vowing to kill her when he returns. After multiple failed attempts and an epiphany that results in mending ties with Ringo, Mizu manages to recreate the metallurgy of her sword's steel but refrains from reforging it until she has slain Fowler. Mizu and Ringo leave for Edo to save Akemi and kill Fowler.

Mizu asks Ringo to wait by the sewers while she saves Akemi and sends her his way. Taigen finds Ringo and they decide to storm the front gate to warn the Shogun about the impending attack, which shortly ensues as Fowler’s army breaks through the castle defenses. Seki saves Akemi from her cell, locking her father in her place, but they are outnumbered by soldiers until Mizu arrives. Heiji opens the final gate from the inside, giving Fowler access to the Shogun and his family. Fowler kills the Shogun, but the Shogun's sons and wife escape after Mizu crashes in, leaving Taigen to kill Heiji Shindo. Mizu subdues Fowler after starting a fire while attempting to stop him from fleeing, which rapidly spreads throughout the castle and then to the city.^{[lower-alpha 3]}