Naruto: Crimson Maelstrom of Kirigakure Chapter 2: Recovering, a naruto fanfic

Disclaimer: I do not own Naruto or any related characters. Those belong to Masashi Kishimoto, and things would be a bit different in the manga if I were him. I make no money off this fanfiction, and merely write for the enjoyment of myself and others.

Author's Notes: Hey guys, been a while, ne? I had to help some old ladies cross the road, so that's why this chap is out later than I thought it would be. ;) Naw, really, now that I'm looking at things, it'll probably be two weeks or so between each chapter. Anyway, thanks SO much for all of the great feedback from last chapter; I'm glad most of you like the idea of the story, and enjoyed last chap.

This chapter, we get some time-skips, and find out bits and pieces of what has happened in the intervening years, before ending at the current timeframe of ~12 years after the first chapter. Don't worry though, there'll be plenty of flashbacks in future chapters that detail some of the events we're skipping over right now.

Anyway, hope you enjoy this chapter – please read and review!

Chapter 2: Recovering

Two Months after the attack of the Kyūbi – Konohagakure, Land of Fire

Hiruzen Sarutobi looked wearily over the latest ANBU search team reports a final time before he tossed them back down onto his desk. The news was the same as it had been a month ago – Naruto Uzumaki, along with his mother's body, had disappeared completely and not been sighted anywhere.

Now, Sarutobi had nothing to go on, and a number of civilians and Shinobi in the village breathing down his neck about finding and retrieving the body of their Hokage's wife. He felt a pounding headache coming on at the thought of the upcoming Shinobi-Civilian joint council meeting later in the evening.

When Naruto had disappeared with his mother, the first move Sarutobi had to make was to order him placed in the Bingo Book as a missing-nin – the boy had made it clear, explosively clear that he wasn't coming back. Unfortunately, it turned out from one of his aides checking the records, that an oversight had been made during the mass confusion of the Third Shinobi World War when they boy had come to the village, and he'd never been registered as a Konoha ninja. His mother hadn't either, but technically could be considered a Konoha civilian due to her marriage to Minato. Sarutobi had all of his aides cross-referencing the Shinobi roster with citizenship records to ensure no similar situation had happened with refugees from the war, and prevent anything like what they were currently facing.

While Naruto had done missions for Konoha, he could not legally be labeled a missing-nin, as that required actual induction into the Konoha Shinobi corps. The laws controlling that had been put into place many years to prevent the possibility of declaring civilians or independent ninja or mercenaries as missing-nin if they assisted Konoha (and Sarutobi knew that other villages had similar regulations). The other reason behind the laws was to allow joint missions between allied nations, without the allies worrying about being placed in the Bingo book as a missing-nin if that alliance later ended.

Now, until Sarutobi could think of something else, he could either put Naruto in the Bingo book as a foreign-nin who had participated in the theft of a bloodline clan from Konoha, or keep him from the book entirely and hope something happened in the future. Declaring him to be a bloodline thief, however, caused problems for Konoha itself. At first glance, it would of course make them appear to be weak, allowing such a theft.

But an even greater risk from that existed, and it had been recognized by Sarutobi and the elders: if they advertised such a theft, the other countries would certainly hunt for Naruto, but not for 'doing a good deed' and getting Konoha's bloodline back for them, but instead to gain access to the bloodline themselves. Entering him into the bingo book for that would be tantamount to handing over two of the last Uzumaki in the world to whatever Hidden Village got to them first.

Sarutobi heard a familiar 'click-click' of wooden geta on his windowsill, and waved a hand under his desk, sending chakra to de-activate the alarm seal that had been set off by the arrival, so that the ANBU would not storm into the office to attack the intruder.

"Can't you arrive through the door like normal people?" Sarutobi asked, raising his gaze from his paperwork to the man crouching in the windowsill.

He was younger than Sarutobi, somewhere around 40 years old. He had long, nearly waist-length white hair that hung in a ponytail, with two long bangs framing his face. Red streaks ran from his lower eyelids, along his cheeks and down past his chin, and a large metal headband with the kanji for 'oil' adorned his forehead.

He jumped down from the windowsill, his red cloak swirling around the green short-kimono and green pants he wore underneath it, and he grinned. "Now, is that any way to greet your favorite student, sensei?"

Sarutobi shook his head wryly. "Have you found anything, Jiraiya?"

Jiraiya was known in Konoha as the Toad Sage, and known well throughout the world as one of the Three Legendary Shinobi, the Sannin – sharing that honor with Sarutobi's other two students, Tsunade and Orochimaru.

Jiraiya's grin dropped, his expression becoming serious. "No, sensei. I've been in contact with all of my sources. The kid has gone to ground, and done it well."

Sarutobi sighed, and lit his pipe, puffing on it slightly. "We've had the same luck. The best we can hope for is he eventually resurfaces, I think."

Jiraiya shrugged. "Maybe. My best bet is he'll eventually join a village. That and find someone to try to heal his mother."

"Tsunade, do you think?" Sarutobi asked.

Jiraiya nodded. "I'd put some sort of watch on her, in case he approaches. She is the best medic out there. Make it discrete though, so you don't get her pissed off at you for watching her." He reached up and rubbed at his ribs at phantom pain from the one – and only – time that Tsunade had caught him peeping on her.

Sarutobi looked down at a long roster book on his desk, and idly flipped through it. "Perhaps an Inuzuka," he muttered softly. They'd be able to remain further away, avoid tipping off either Naruto or Tsunade, and rely on their chakra-sensing and scenting abilities.

He glanced back up at his old student. "Anything else?"

Jiraiya frowned. "There's something going on in the underground, talk of some mercenary group forming up, with some heavy hitters." He shook his head. "I'll look into it. I did come here for something else – to say that I wish I'd been here to tell you what a stupid idea this whole business with Naruto was."

Sarutobi rubbed his forehead. "I know, Jiraiya, I know. There was little I could do about the girls, and it seemed to be the best option available at the time. In hindsight…"

Jiraiya interrupted with a wave of his hand. "I'm not talking about keeping his sisters from him – that's its own issue. I'm talking about forcing the issue of letting Kushina die. She was Naruto's world. Everything he did revolved around her. He was hostile to Minato – of all people – when he first married Kushina. I eventually told Minato – when he came to ask my advice on what to do – to have a talk with him and ensure him he wasn't trying to steal his mother away from him, and the kid finally mellowed out."

"He'd already been told he 'lost' his sisters and then the doctors were threatening the basis for his existence, and you and the elders were siding with them. You triggered his fight or flight response, and he's smart enough to realize he couldn't fight the village on this, so he ran. And I don't exactly blame him," Jiraiya finished, his expression grim.

"I realize that now." Sarutobi said. "But there's little that we can do about it."

"I think if you had talked some sense into the civilian council about the girls – if Naruto had known they were alive – I think he would still be here today." Jiraiya stated, crossing his arms, still wishing he hadn't been away for this whole thing. And wishing even more that he'd been there to stop Minato from sacrificing himself, to take on that burden in place of his student.

"I realize we've made mistakes, but now the question is – what do we do going forward? There is very little in his files, but what is there shows him to be a competent Jōnin, who can lead a team. You interacted with him when you visited Minato, far more than I have. Is he a threat? Or perhaps the better question – how much of a threat is he?"

Jiraiya sighed, and scratched the back of his head. "I really don't know the best way to answer that, sensei. The Uzumaki clan always started training their kids earlier than we do, simply because their chakra reserves are so big that they're large enough to perform jutsu much earlier than many other people. Naruto, though, Kushina started him even earlier than most Uzumaki. I'm not sure why, but I suspect it was whatever happened with Naruto's father. Whenever I asked her, she would only tell me that she wanted him to be able to defend himself and those he loved."

"His own natural aptitude for being a Shinobi probably played a part as well," Jiraiya continued. "That kid was so smart, it was scary sometimes, sensei. He was a true genius… he reminded me a bit of Orochimaru…." Jiraiya trailed off, remembering his own Genin days and how much better than him Orochimaru had been. "And, well, he had enough power to already make it to Jōnin."

"Power is one thing. What I need to know is what skill he is capable of," Sarutobi said, wishing he'd not let himself fall out of the loop so much since he'd decided to retire and eventually chose his replacement.

"I visited a few times when Kushina was training with him, and some of those things… it was like watching the ANBU entrance exam going on every day," Jiraiya said. "You know how scary she was on the battlefield – probably almost second to Minato, at least in this village – well, she's taught him most of the things she knows, including a lot of Fūinjutsu, which can be pretty deadly in its own right."

The ANBU entrance exam was well known as one of the most grueling experiences any Shinobi could ever go through. Even ANBU daily training paled in comparison to the entrance requirements, which had been put into place to weed out anyone unfit for the duty.

"Bottom-line, Naruto's already a Jōnin, and I know for a fact that the ANBU had already decided to make him a member when he was old enough. He's going to be a very powerful ninja. He'll be a threat to anyone he views as an enemy. I went out to where you said those searchers found Danzō, and whatever he used, Danzō's lucky he's only in the hospital for a few weeks." Jiraiya concluded.

Sarutobi sighed. "Unfortunately, we can't place him in the bingo book right now, even with the attack on Danzō." He shook his head. "Damn fool still hiding his Root from me. If it had been a sanctioned pursuit, we would have something."

"I know, sensei. How's the old coot doing, by the way?"

Sarutobi sighed at that. "As well as can be expected. He lost his right arm, and the doctors said his leg was little more than jelly with the amount of breaks to his bones. He'll likely be walking with a cane once he's able to walk again."

Sarutobi frowned, then. "You've given me a lot to think about on Naruto. Even his teammates did not have a good grasp on how strong he was. So, he is a serious threat – but will he be a threat to our village?"

Jiraiya shrugged. "Like I said, he'll be damned dangerous to anyone he views as an enemy. Fortunately, you didn't manage to do anything to Kushina, so right now he probably views us as an annoyance. But if he ever finds out the truth about his sisters…" Jiraiya trailed off, staring hard at his sensei, not even needing to complete the sentence.

The Hokage nodded. "I'm already drafting a law to keep this from spreading. No one will be allowed to talk about the Jinchūriki or their status to anyone who doesn't already know. I had already been planning this anyway, as there have been several attempts on the girls already by people who have lost loved ones and want revenge on the Kyūbi, and I don't want that passing down to the next generation. The official story to anyone under the age of five, and to any foreigner, is that the Yondaime managed to kill the Kyūbi."

"With the side benefit of spreading the idea that Konoha produces Shinobi strong enough to kill a Bijū," Jiraiya said with a slight grin. "I'll keep an ear to the ground with my network, make sure that if we start hearing about the girls or anything related to them outside of the village, we can act quickly and weed it out before it spreads. We don't need the threat of a revenge-obsessed Uzumaki targeting us."

Jiraiya moved back to the window. "I'll leave you to have fun with your council meeting tonight," he said with a wink. "I've got some research to do for a new book I've started writing."

"I'm sure it will be good," Sarutobi said with a slight smile – he'd been one of the few who had bought his student's book, "Tales of a Gutsy Ninja", which had failed to become a best-seller.

"I'm very sure you will," Jiraiya said with a mysterious grin as he leapt back out the window, and into the streets below.

-oOo-

7 Years after the attack of the Kyūbi – Konohagakure, Land of Fire

The young red-haired girl jumped as a loud crack of thunder rolled through the village, shaking the windows of their tiny little apartment. Heavy rain beat at the windows, whipped to a fury by the howling rains. Every year in Konoha saw at least one major storm like this one – one that kept even the hardiest individuals inside. Out in the village, even most of the Shinobi guarding the gates of Konoha were sheltered inside their guardhouses.

A loud thump made the girl jump, and grab wildly for her sister's hand across the bed in the dark of the apartment. The thump was followed by several more, until a staccato beat drummed across the roof as the rain turned into hail – some pieces nearing the size of the girl's other small fist, which clenched the blanket.

"K-Kasumi-nee-chan," she whispered softly.

Lightning streaked across the sky, lighting up the room, and illuminating its occupants. The young redhead, cowering under the covers of the bed in her pajamas, reaching out for comfort from her twin sister.

Kasumi smiled at her sister comfortingly, and squeezed her hand. She shook her head slightly, her long blond hair bouncing at the movement as she scooted across the bed, and put an arm around her sister.

"Don't worry, Karin-chan, it'll be fine. There's nothing to worry about, little sis. Remember, I'll always protect you," she said, as she tried to hide a shake in her own voice.

She'd taken the role of big sister early on, though being twins, they had no idea which one was truly the oldest, and even old man Hokage told them he wasn't sure. But she'd taken it on anyway, and enjoyed it to the fullest, glad that her sister looked up to her like she did, and she took her job of protecting her little sister very seriously.

It was times like these, even when she was shaking in fear at the horrible storm, that she put on a calm face to comfort Karin, though she wished someone else were there to comfort her – comfort them both. But they were orphans, and all they had was each other.

Kasumi squeezed Karin in a hug as she felt the other girl shake against her and then switch her other hand from gripping the sheets, to tightly gripping Kasumi's orange pajama shirt.

Kasumi stroked her sister's messy red hair, and hummed a low tune she'd once heard a mother singing to her child in the park, and she tried to drown out the noise of the storm for herself and her sister.

The relative peace of the moment was shattered suddenly by a crashing sound on the other side of the wall – debris breaking a window in the apartment next to theirs – followed by startled shouts and voices muffled by the wall.

The howling of the wind outside picked up, and the windows began to shake, and both girls gripped one another more tightly. Kasumi was nearly shaking as much as her sister now as a low siren sounded through the village, indicating that the few brave souls up on the walls had sighted a tornado in the area.

Suddenly, a feeling of warmth and calm passed over Kasumi's body, and her stomach began to glow a golden color, visible beneath the sheets. Slowly, golden chains of chakra began to emerge, and light up the room to the girls' astonished eyes.

The chains swayed in the air like snakes, and then began to wrap around the entwined bodies of the twins, cocooning them in the warm energy they emitted. Other chains seemed to slide around the room, and become rigid, while emitting a low glow of energy from one chain to the next, to slowly create a dome of protective energy around the room. As each chain slid into place, the noise from outside dimmed as the energy seemed to dampen and insulate the area the chains now surrounded.

"Kasumi-nee-chan?" Karin asked, looking up at her sister her wide, red-irised eyes, only to see an identical expression from her twin.

"I-I don't know Karin-chan, I don't think I did anything…." Kasumi said, her own gray-blue eyes moving down to her stomach where a glowing seal was outlined – the same place from which the chains were all emerging.

Karin closed her eyes, and shivered slightly at the strength of the chakra she could sense coming from her sister, and from the chains. "Really strong," she muttered, reaching out to touch one of the chains. A feeling of peace, of being caressed lovingly, flowed over her – and she felt, rather than saw, a seal on her own stomach light up.

The chains slid into their final places, and the roar of the storm outside dulled to a light whisper, while the chains that had encircled the girls drew tighter, pulling them closer together.

One last, strong pulse of warmth and caring pulsed across their bodies, so tangible it was almost as if they could hear words attached to it: a message of 'Be calm, you're safe now.'

Karin smiled up at her sister, before yawning slightly, and resting her cheek against Kasumi's shoulder, the storm outside now all but forgotten. Whatever this was, whatever power Kasumi had, they knew they were safe now. "Thanks, nee-chan," Karin muttered sleepily, her eyes fluttering shut.

Kasumi pondered the feeling that had washed over them once more, and then finally shook her head, and leaned down to kiss Karin's forehead before she carefully removed the glasses from her sister's face, and reached back through the chains that surrounded them to set the thick-rimmed spectacles on the night stand.

Whatever it was, it felt like they finally had something – or someone – looking out for them just like she'd wished for, Kasumi thought to herself as she leaned her head to rest it against Karin's, and drifted to sleep in the peaceful silence that masked the storm that continued to hit the village around them.

-oOo-

8 Years after the attack of the Kyūbi – Near the Land of Water

Naruto gasped for breath, and he let his companion's arm slip off his shoulder as he sat him down on the shore, far enough inland that the waves weren't lapping up against them. As fit as a ninja could be, practically carrying someone bigger than you, along with a sword nearly your own height, across several miles of ocean, was tough.

"C'mon," Naruto said between breaths as the man lay back on the beach, his skin paler than Naruto had ever seen it get.

His companion grunted, and shook his head, hand reaching down to the gangrenous black skin surrounding a large puncture wound on his bare stomach. The patch of dying skin had been the size of a finger when they'd started out, now it was the size of Naruto's hand.

"No, kid, this's as far as I'm making it. Shhhhit!" he hissed out. "Little fucker got me good. Should've been more careful, knowing who his partner is." he rasped, leaning his head back against the large shape of his sword. "No healing this one, we already tried. Whatever that bastard had on that knife, it's eating at my guts, and not letting me heal anything."

Naruto bit his lip and growled, trying to lift the man again, his nearly shoulder-length head of messy red hair obscuring his vision as he bent down. But the man resisted, even weak as he was.

"Damnit, sempai, there might be something in the scrolls that can help." Naruto said.

The man closed his eyes briefly, and coughed, and Naruto could see blood on his sharp, almost shark-like teeth when he opened his mouth to speak. "Face it Naruto, Sasori's poisons, mixed with whatever else that damned snake had on that dagger, aren't something you can fix. Should've figured him and that slimy bastard Orochimaru being partnered together was bad news. Don't know how they figured out I was finally leaving," he said, glancing down at the tattered remnants of a black and red cloak that hung from his waist, the only other signs of the long fight he'd been in against the other two S-Ranked Missing-nin.

He reached up and gripped Naruto's shoulder firmly. "Listen kid, I know we didn't get off to the greatest start, but… just wanted you to know you were right." He coughed out a laugh. "First person I ever said that to, but it's the truth. You made me see that not everything in the world is a lie. And you're still a fuckin' snot-nosed brat, for making me say that now."

Naruto laughed softly, and placed a hand on his sempai's forehead as his eyes closed, touching the scratched-out Kirigakure forehead protector. "Thanks. You're still an old geezer."

He chuckled wetly, and opened his eyes again. "I know you have your own goals, with your mother. When you're done, kill those two bastards for me. And see if you can do what I couldn't… with Kiri."

Naruto lowered his head. "I swear, sempai, Sasori and Orochimaru will die."

He sank his head back, grimacing in pain as the poison continued to attack his body. "My sword… you've learned everything I've got to teach you… she's yours. You're a Swordsman of the Mist now, kid..." His voice trailed, and there was a rattling sound to his breathing.

"Sempai?"

"You earned it. It's your birthright, Naruto."

Naruto's brows furrowed. "Unless this is one of those 'Naruto, I am your father' moments – and I'm pretty damn sure you aren't, even if you're a geezer – I don't understand…."

His companion shook his head. "Not like that, dumbshit, I never told you… looks like your mother never did either… Wish I had more time, but, your clan, kid… they made the swords, or that's the legend at least. Gifted them to Kiri as part of an alliance before the First War. Take the sword, she's yours." He reached up to grip the handle one final time, before he looked back up at Naruto, who stared back at him with wide eyes.

"Thank you, for this and… for telling me that," Naruto said, as his mind raced at the idea that these swords – this sword – were made by his clansmen perhaps over a hundred years ago. Another link to his family and clan, revealed just when he was about to lose someone who he had come to think of as an older brother.

"When I… when I'm…" He was seized with a coughing fit, his fist coming away from his mouth covered in blood. "Ocean burial, kid, it's where I belong. And Naruto, crazy as it'll sound, I've actually got faith in you - I know you'll figure out a way to bring her back – you never break your word …. And y'know …. I'd still tap that, if she was awake," he said, teeth bared in a wide grin, before the light left slowly left his eyes, and his body relaxed as his life left him.

"Asshole," Naruto muttered fondly, as to keep his tears contained, and reached up to gently close the man's eyelids.

He looked up, and out over the ocean, hatred in his narrowed eyes as he stared in the direction his sempai had come from. He pulled out a kunai, and slashed a line across his palm, letting his blood pool in it before turning his hand, and clenching it into a fist. He lifted the tightly clenched fist up in challenge.

"Orochimaru, I trusted you once and nearly lost my mother, and now you've helped take my brother's life. Sasori, you think yourself safe, hidden behind your spies and poison and puppets, but I'll be the one to prove to you how foolish that belief is. I swear that your deaths will not be easy. They will not be quick. And they will be at my hands, and you will suffer," he swore, letting his blood spatter across the sand of the beach, a dark crimson in the light of the sun as it set across the shattered ruins of his home country, which stood behind him.

-oOo-

12 Years after the attack of the Kyūbi – Kirigakure, Land of Water

Naruto awoke slowly to the feeling of warm breath against his neck, and an even warmer body pressed up against his side. He cracked open his eyes, and turned his head. A pair of warm green eyes stared back at him, one eye partly covered by one of his companion's long auburn bangs.

"Morning, Mei-chan" Naruto said, stretching slowly, careful not to pull away.

Her pink lips quirked up into a smile. "Sleep well, lazy?" She asked, letting her long, slim fingers trace a pattern on the bare skin of his chest.

"After last night? Of course. You always tire me out, hime." He said, grinning.

A dusting of red appeared on her cheeks, and she shifted to rest her chin on his shoulder, so she could nuzzle her nose against his neck. "You're one to talk. It's gonna be a long, sore day behind the desk."

Naruto chuckled, and lifted an arm slightly to mesh his fingers with the ones she was moving slowly along his chest. He glanced over at the clock next to the bed, and groaned. "We've gotta get up, hime. You're supposed to host that trade meeting. If you're late, Zabuza will never let us hear the end of it."

Mei sighed heavily, and nodded. Zabuza might seem to most people as a hard, uncaring man, but there was another side that only his friends saw… one that would tease the two of them mercilessly about their relationship, especially if they were late for something like this.

She pressed her lips to Naruto's cheek, and then slowly sat up, getting off the bed.

Naruto's eyes followed her with interest, her nearly ankle-length red-brown hair dragging along the bed before it settled into place, blocking much of his view of her shapely form.

A satisfied grin spread across his face as he closed his eyes, hearing her turn on the shower. Soft footsteps sounded moments later as she returned to the room.

"You should get going too, Naruto-kun," she said, poking his side gently.

His eyes snapped open, and he sat up quickly, grasping the hand that had poked him. "As you wish, Mizukage-sama," he said teasingly.

She rolled her eyes. "I wouldn't be Mizukage, if it weren't for you. We'd still be fighting against Yagura and his men right now… my brave Swordsman," she said the last with a husky note to her voice, before she leaned slightly closer to trail lazy kisses along his neck and up to his lips.

Mei deepened the kiss, moving her free hand up into his hair, her blue nail polish clashing with his long red locks. She sighed slightly as she pulled back several long moments later, and her eyes met his once more. "I'll have a mission for you, Naruto-koi, to keep you busy while I'm in these trade meetings for the next week. There's a missing-nin – one of Yagura's Jōnin that escaped the battles – up in the Land of Frost. We think he's going to try selling Kirigakure's secrets – he's already asking around to see who's interested."

Naruto nodded, though hesitantly. "How long do you think it will take?"

She shrugged, looking at him curiously. "That's up to you, why?"

"At the end of the week…. It's that time." He said, his gaze moving over to the window that faced north – toward Konohagakure.

Mei's eyes softened, and she reached up to caress his cheek with the back of her hand. "I'm sorry, I've been so busy, I forgot. Finish things up as quickly as you like – Konoha is on your way back anyway. Do you want me to cancel things today so we can go visit her before you go?"

Naruto smiled weakly, a pained look barely visible in his gaze. "No, Mei-chan, I'll visit when I head off today – you stay here and get this village the trade agreements it needs. I'll be fine."

Mei leaned forward, resting her forehead against his. "I'm sorry my clan's medical scrolls didn't help. I was sure they would have something, with our past ties to Uzushio and all..."

Naruto nodded against her, and kissed her lips lightly. "You've already apologized a dozen times, when there's nothing for you to be sorry for, hime. Thank you for trying though…. And understanding. I'll find another way…. I have to." He said softly, as he took in his lover's presence as she nodded her head against his chest.

She'd been one of the few people he'd ever told about his mother, and the only person besides himself who knew where she was hidden while he spent the last decade searching for a way to revive her. Mei, who was 7 years his senior, had become his lifeline, the only thing that saved him from spiraling into a much darker place, and he couldn't thank her enough for being there for him for these past five years – first as a friend, and now as his closest confidante and lover.

The Terumi clan had been one of the smaller clans that made up the village of Uzushiogakure, and being with her felt like at least a small piece of his heart had been restored. And now Kirigakure was starting to become a real home to him. He could only pray to the gods that he didn't lose this one as well.

Mei smiled warmly, and rubbed her forehead against his. "I'm certain you will, Naruto-kun. But for now - care to join me in the shower?" She asked as she pulled back, and began to walk slowly toward the bathroom. She paused only to glance over her shoulder her eyes hooded and smoldering.

Naruto growled in the back of his throat at the sight of her swaying hips, and heard her laugh as he quickly got up and followed her to the next room.

-oOo-

Kirigakure, Land of Water

Naruto stepped out into the covered courtyard that encircled the core of the Mizukage Tower. It was a large, long walkway under the roof of the enormous round building, and various plants grew along it, with open windows on one side of the walkway letting in the cool morning air of Kirigakure.

He put his arms up behind his head, and took a deep breath of the air. He smiled slightly at the low hum of activity that could be heard through the open windows from the city. The sounds of rebuilding were much more peaceful than the sounds of war which had filled these streets not so long ago.

Naruto considered taking the stairs down to ground level – or rather, the level of the large raised platform surrounding the Tower, keeping it well above the somewhat marshy ground surrounding it – and then decided against the tedious trek.

He instead walked over to one of the open windows, and paused a moment as he looked out over the city: large, tall round buildings with many windows, and trees and plants growing from their roofs stood nearby – the housing for the hidden village's Shinobi. Smaller, more squat buildings only a few stories tall were visible out further into the marshy forest that surrounded the city, which contained many of the other Shinobi facilities for the city.

Inward, toward the city proper, buildings of various sizes and shapes filled the area, and he could see numerous large construction projects going on to build and repair important buildings in the village. Down below, on the cobble and dirt streets of the city, thousands of villagers went about their daily lives.

To the far north, on the opposite side of the village from where he stood, he could make out the outlines of tall, craggy mountains – that surrounded the north, east, and west of the village – through the thick fog and mist that gave the village its name. Only to the south was the terrain not so foreboding, and even then, it was miles of swamp and forest, with only a few elevated and dry trade roads on which their commerce traveled.

Naruto glanced down, and then dropped the nearly 60 feet down the main face of the Mizukage tower, slowing his descent slightly with a chakra-covered hand applying some pressure to the stone face of the tower. He landed in a low crouch, and then began to walk toward the nearest tall building, where his quarters were, patting his pockets to make sure he'd remembered to bring all of his things from Mei's room.

As he walked along the large, raised stone platform, glancing down from time to time to see the low river that ran through the large culverts under his feet – made to carry a much larger load that would be seen during the floods brought by the spring monsoons that plagued the region.

A ramp led down from the main platform, down to the entrances of the apartments set aside for Shinobi of the Mist, and as he neared his building, he grinned when he saw a figure out on the courtyard that surrounded the building.

A young teen around 14 years of age, wearing a pink, sleeveless and low-cut kimono, knelt in meditation. She was a slight girl, with long black hair that settled down around her shoulders, framing a beautiful face and contrasting with her pale skin. She had her hands held out in front of her, a fist-sized ball of water hovering inches above them – a paper-thin layer of ice covering the surface as the water inside rotated slowly.

"Ohayo, Haku-chan!" Naruto called while still a several long strides away.

Haku's large, dark brown eyes opened slowly, and the ball above her hands slowly crystallized fully into a ball of ice before she let her chakra lower it into her hands.

Her eyes finally focused on him, and she lowered her head slightly in a nod of greeting. "Good morning, Naruto-sama. How did you sleep?"

"Very well," he said with a wide grin, and saw a faint pink dust her pale cheeks – she was one of likely only a handful who knew of his more…. intimate… relationship with the Mizukage.

He nodded to the ball of ice in her hand. "I see your chakra exercises are coming along nicely?"

She turned the ice slowly in her hands, and nodded. "Yes, thank you for teaching me them, Naruto-sama. I have found that I am able to form my ice much faster, and with less effort than before."

Naruto grinned, and reached down to pat her head. "Keep working on it – I've got another family scroll on advanced chakra exercises for you. I'm going off on a mission, but I'll be back in a week or so. Let's have a spar then and see how much you've improved, and I'll give you the scroll then."

She smiled warmly, her eyes lighting up. "I look forward to it. I will keep working on it, to make you and Zabuza-sama proud."

"Speaking of No-Eyebrows," Naruto said, "what's he up to? Thought I might get his insight on the mission I'll be taking, get an idea of who I'll be up against."

Haku smiled apologetically. "Zabuza-sama is already in the city. Several of the officials for today's meeting arrived early, and asked for a tour of the city, so he was stuck showing them around," she said, her voice barely containing a soft laugh.

Naruto guffawed at the thought. "On second thought, he's probably not in a good mood having to play tour guide and host, and definitely won't be happy to see me with me keeping Mei-chan, erm… busy…."

Haku's eyes danced, and she shook her head. "You are right, when I saw him, he was muttering something about scalping you."

"Oh well," Naruto said, scratching his head. "I should get going then, get packed and get my mission before he hunts me down. Goodbye, Haku-chan, see you when I get back," he said, ruffling her hair once more, before walking into the building.

Naruto had met Haku and her teacher and companion, Zabuza Momochi – The Demon Of the Hidden Mist, and one of its famed Seven Swordsmen, wielder of the sword Kubikiribōchō (Decapitating Carving Knife) – several years back.

At the time, they'd been missing-nin, much like Mei and her rebels. Naruto, one of several who she'd sent in search of allies in the rebellion, had gone looking for Zabuza, as he had learned the man had attempted a coup of his own.

Unfortunately, Zabuza and Haku had seen the Kirigakure hitai-ate he'd received when he joined the rebels, and believed he was after them to collect the bounty on Zabuza. Before Naruto even got the chance to explain why he was there, he had been pulled into a long, intense fight with Zabuza. That was where he learned that Zabuza' moniker of Demon of the Hidden Mist had been well earned, and well deserved. He'd lost an arm in that fight – fortunately his Uzumaki bloodline allowed it to grow back within a few days – before he had managed to get the advantage for a few minutes, and gain enough time to explain himself.

He knew he likely could have taken Zabuza in a straight up fight, and likely win, at his current level and perhaps even back then, but he'd had to hold back in the fight as he didn't want to kill the man he was trying to recruit. Truthfully, it was likely only the fact that he wielded one of the other Seven Swords himself, that he'd been able to get the upper hand and end the fight.

Once their misunderstanding was cleared up, and after a bit of persuasion, Zabuza finally joined their efforts to overthrow the Mizukage. Over that time, he and Zabuza had become comrades and even friends. And much the same had occurred between himself and the young prodigy who Zabuza had taken in and raised – she was the last of the Yuki clan, the only one of that family of ice-users to escape the Kekkei-Genkai massacres brought about by the previous Mizukage's regime.

Naruto bit back a sigh at a stabbing feeling in his chest. He and Haku had developed a somewhat sibling-like relationship – though perhaps more akin to him being her uncle, with her insistence on labeling him 'Naruto-sama' and how she treated him with nearly the same measure of respect and admiration as she did Zabuza. In either case, sometimes it reminded him of what he was missing – what he'd lost that day 12 years ago, what he could have had if his sisters had lived.

He stopped a moment, closed his eyes tightly, and shook his head. These stray thoughts always tended to pop up more frequently every year this close to the anniversary of the attack. He took a deep breath, and then continued up several flights of stairs to the fifth floor, and slid his key from his pocket.

He put the key into the lock, and then placed a hand on the door where he'd placed several dozen seals. A brief pulse of chakra confirmed none had been tripped, and no one had tried to enter his room. Some might think it paranoid, but he was simply careful – there were few he trusted, and it always paid to be cautious.

He deactivated the seals with a quick twist of his finger and the chakra he'd pulsed into them, and entered his apartment. It was modestly furnished, and no bigger than the rest of the apartments in the building. He slipped off his shoes in the entryway, and turned to close the door, and lock it behind him.

He pulled off his wrinkled shirt, and tossed it across the room onto a basket filled with clothes waiting for him to take to the laundry and clean. As he rounded the corner past the small table next to the kitchen, a skittering sound was his only warning as a figure launched itself from the open door of his bedroom down the short hall, and slammed bodily into him, nearly knocking him off his feet.

"Damn it, girl, give me a little warning," he said, wincing at the sharp scales of the creature that had rammed into him as they scratched his bare chest.

Samehada was a long – over four feet at the moment – and rather heavy being. Dark grayish-blue, razor sharp scales covered the entire body of the sentient sword that had become his partner almost four years ago to the day with the death of her master and the man Naruto had learned so much from.

The sentient sword could change shape, and even grow, but generally remained at this size, with a shape of an almost cylindrical greatsword, just about matching Zabuza's own sword in size, and several feet in diameter. Near what would normally be the tip, or end of the sword, the scales opened up to reveal a mouth filled with sharp teeth.

A long pink tongue extended from the mouth, and licked Naruto messily on the cheek as the sword's body vibrated in greeting, scales clacking against one another.

"Agh! Okay, okay, girl, sorry I haven't been paying much attention to you. I promise, you'll have a good feeding soon, okay? We've got a mission."

A trilling sound echoed from Samehada's throat, and he felt a slight tug on his chakra as his sword nibbled at it. It had seemed Kisame was right about the Swords being created by Uzumaki. However it was that they had managed to make Samehada, the sentient sword had always seemed very attracted to his chakra, even when Kisame had owned her. And now, he'd found that she'd become much more active – as well as affectionate – toward her new owner than anything he'd seen from the sword before, even when Kisame went on a killing frenzy.

Whether it was the taste of his chakra, or the large Uzumaki reserves he held, he didn't know, but he wouldn't complain. The creature had become more than a sword, even more than a pet, to him – Samehada had become one of his closest companions, as weird as some might view such a thing.

He ran his fingers across the scales of her head, careful to run them with the grain so they didn't get cut on the sharp scales. He winced slightly as Samehada moved the scales that allowed her to cling to his body, and shifted the longer scales – almost like dozens of tiny feet – and climbed up his chest until the bulk of her weight rested on his shoulder.

The flexible 'hilt' at the opposite end of Samehada's body, wrapped around his arm as the sword settled into place. The 'hilt' looked at first glance to most people to be an ordinary leather-wrapped sword hilt, built into the tapered end of the sentient sword. But in reality, it was essentially an extremely flexible prehensile tail, protected by hard brownish, interlocking scales, and capped with a bony protrusion at the end that looked rather like a miniature version of a human skull.

Now that Samehada had anchored herself in place across his shoulders, he was able to move freely through the apartment. It had taken him close to a year to get used to carrying and using Samehada due to the extreme weight of the sentient sword. The fact that the sword didn't cut in a normal sense, but rather shaved away at the flesh when used correctly, had also made him adjust his fighting style, though he'd found that the training with a large flail that Kisame had been tutoring him in helped greatly in adjusting to the sentient sword.

Now, though, he'd fully built up the muscle mass and strength needed to bear the sword correctly, and his large chakra reserves due to his ancestry let Samehada easily feed off of his own chakra without any strain to himself.

Naruto entered his bedroom, and pulled on a pair of long blue shorts that extended down several inches below his knees. A pair of light, striped leg-warmers that were common Kiri-nin attire covered the rest of his leg, and overlapped slightly with the shorts. He slid on his sandals, and then bid for Samehada to crawl back off of him and onto the bed while he put on a sleeveless black shirt, and similarly-colored fingerless gloves.

He bent down to pick up his flak vest, and slid it on. Unlike Konoha's flak vests, Kirigakure's were a slate grey in color rather than drab green, and had noticeably longer shoulder pads. His last accessory was a now well-worn Kirigakure hitai-ate, which he tied across his forehead – where it helped greatly in keeping his hair held back away from his face.

Naruto smiled when Samehada gave a questioning trill. "Yeah, I'm ready. Let's get you wrapped up for the trip, and we can go get the mission scroll," he said, as he reached for a large roll of bandages he kept in the pocket of his flak vest.

-oOo-

Near the Land of Water

A shard of pottery crunched underneath Naruto's sandal as he walked through the jumbled ruins of Uzushiogakure. Buildings that once stood proud and tall were now shattered remnants fo their former glory, and large pillars now rested on top of what were once houses, knocked loose from where they had once sat. At one point, years ago, he would have been walking on the bones of his clansmen and others who had lived in his home village. It had taken some time, since his first visit back here years before, but he and an army of shadow clones had given them all a proper burial – though many were still probably buried beneath the shattered buildings of the city.

He reached the center of the city, and then closed his eyes, stretching out his senses to ensure he hadn't been followed. He only moved when his own scan was complete, and he received an affirmative growl from Samehada – she was by far a better sensor than he was, able to detect even most of those who tried to mask their chakra, a skill very few were truly capable of doing completely.

He moved to a large, now-destroyed fountain that took up much of the space in the center square of the city - he vaguely remembered playing in it with his mother when he was a toddler. Once Naruto was standing in the basin – which was filled with a few inches of brackish rain water – he pressed his hands against two specific spots on the weathered fountain, and forced chakra down into the marble surface. Intricate and glowing seals sprang to life on the stone surface, and he twisted and manipulated the seals until the right array was created. He sent another pulse of chakra into the seals, and they responded to their new orientation by 'unlocking' that which they sealed.

The enormous marble fountain rumbled and a portion of the center pedestal of the fountain – which had once held up intricate sculptures of various sea creatures that shot water from their mouths – slid open to reveal a narrow entrance, and an even narrower set of stairs that led down underneath the streets of the city.

Naruto stepped in, careful to not hit his head on the low ceiling, and began his descent down the steps. The entrance slid shut behind him, and he was forced to reach out along the wall in the darkness and send chakra into another seal array, a cascading array that ran the length of the passageway. Torches along the path of the array lit up as it activated, lighting the way downward.

This was one of the village secrets, an entrance into the emergency Shinobi command post, used during an invasion. He'd searched for the entrance for days, only having vague recollections of the stories his mother told him as he grew up – being only a Genin when they'd left, he'd never been privy to it or the entrance locations. Eventually he'd found it, and it had since become his base of operations, well before he'd ever become a Shinobi of the Mist.

The cool gray stone became damp as he reached the bottom of the staircase, and the air was noticeably colder as he stepped into the underground complex. He came out into a large, high-ceilinged room that had its walls lined with similar doorways to staircases and tunnels that led out to other parts of the city.

His footsteps echoed in the large room as he strode across it and into the armory and scroll library, which had still been partially stocked when he'd arrived, and now was filled with his own additions to it.

The next room had been the operations center, with several large video screens still on the walls, hooked up to cameras that no longer existed. The generator that ran the power-intensive equipment sat in the corner, silent for over a decade.

Naruto passed the communication equipment, which would have been used to contact Shinobi out in the city, and exited into another, darker room which had once been a holding area to hold and interrogate captive enemies.

He strode over to one of the cells, and slid his palm over the lock. The door opened to the stench of human filth and sweat. In the corner, sat a middle-aged Shinobi, rocking back and forth on his knees and staring silently at the wall. His long, tangled hair and unkempt beard were testament to the fact that he'd been here several weeks.

Naruto knelt beside him and carefully removed the intricate seal he had placed on him – one that mimicked the effects of being in a sensory deprivation chamber.

The man gasped, and fell backwards, trying to cover his eyes and ears at the sudden onslaught of his senses that had been denied him.

"Now, Hozuka, are you ready to talk this time?" Naruto asked, grasping the man's arm and forcing it away from his eyes while he scrunched them shut as tightly as possible.

"Yes! Yes! Please, I'll talk! I'll tell you anything you want! Please, just promise me you won't use that on me again, please!" The man said, sounding rather frantic.

Naruto's eyebrow rose – perhaps he'd left it on a bit too long, but the man had refused to talk when he'd last come here. "Alright, Hozuka, I swear I will not put that seal on you, or torture you any more, if you give me everything you know. Where is Orochimaru?"

"I, I don't know."

Naruto growled, and the man tried to shrink back.

"Please, I'm telling the truth. His headquarters are in the Land of Rice Fields, he calls his organization 'Otogakure', but he has so many different hideouts, and he's always moving from one to the next. No one person knows where more than three of them are. I've worked in two of them, I can show you where they are." Hozuka said desperately.

Naruto made a noise of acknowledgement in his throat, and picked Hozuka up by the arm, dragging him over to the wall where he'd placed the map of the Shinobi land the last time he'd visited. He pulled a brush from one of his pockets – one he used quite often for making seals – and dipped it into a vial of ink, and handed it to the man, who carefully examined the map, and placed two dots within the boundaries of the Land of Rice Fields, while explaining the specifics of how to find each of them.

Naruto finally nodded, filing the information away in the back of his mind. "Now, what has he been up to? You've only been away from him for a few weeks now, so anything you can give me could still be of use to me."

"I-I-I really don't know. Orochimaru-sama is very private and secretive. He usually only speaks with his scientists, and with his test subjects…. But I have heard rumors that he is planning something that might involve the Kyūbi."

Hozuka shrunk back again as Naruto's eyes hardened at the mention of the Kyūbi. "Could it be reforming already? It's been twelve years since Minato defeated it…" Naruto murmured.

'Is it even possible for it to regain its chakra after being sealed away into the Shinigami?' Naruto thought, his mind racing. 'Or did he find some way to undo whatever Minato-san did, or a way to summon the Shinigami himself?' The latter sounded like something Orochimaru could have stumbled upon, Naruto knew he was obsessed with immortality so more than likely he'd end up coming upon something that dealt with the God of Death himself.

Whatever the case was, he certainly didn't want to meet up with an Orochimaru backed with the power of the Kyūbi. Naruto's eyes lit up, remembering some information he'd tortured from another of Orochimaru's ninja a year ago.

Orochimaru had been looking into the Sharingan and its power… and history told of how Madara Uchiha had once used his own Sharingan to control the Kyūbi during his legendary battle with Hashirama Senju. Perhaps Orochimaru intended to do the same, if he could somehow acquire Sharingan eyes from an Uchiha. Though it would be hard – even Kiri had heard word of the Uchiha clan massacre several years back, largely due to Uchiha Itachi's placement in the Bingo Book.

Naruto glanced back at the man who cowered in his presence. A quick glance at his eyes told Naruto all he needed to know – Hozuka was either telling the truth about all of this, or he was one of the best liars to ever grace the planet.

Naruto's lip curled in a grimace of disgust at the cowardly man who had claimed to be a Shinobi, and served Orochimaru. "I believe you, Hozuka. You're lucky. For a moment there I was considering putting the Senses-Killing Seal on you again."

Hozuka's eyes grew wide with fright at the thought of undergoing more weeks of that torture, but then wider again as he realized that Naruto would keep his promise.

"I-I can leave now? No more torture?"

Naruto forced a smile on his face. "No more torture," he said, helping the man stand.

A sickly, wet noise sounded through the room, and the man's eyes widened even further, his mouth moving without a sound, except for a rattling gasp, and moments later he fell limp against Naruto.

Naruto slowly removed the kunai from the man's chest, and let him slump down to the ground as Naruto wiped the blood from the blade, and returned it to its pouch.

"But you can't leave," Naruto muttered, finishing his sentence as he laid out a large scroll covered with intricate sealing designs. Within moments, Hozuka's body was sealed within the scroll, to be later disposed of properly.

Even an enemy – and a cowardly one who would sell out his comrades, at that – deserved the respect of a proper burial, he remembered his mother teaching him.

Naruto sighed, and turned to the map on the wall. He removed it and rolled it up tightly before he placed it into one of the scroll pouches on his flak vest. Now, there was only one last thing to do – one more room to visit before he left on his mission.

-oOo-

The last room in the complex had served as an emergency medical station. Now, it served a similar purpose - on a large bed in the middle of the room, rested the still form of Kushina Uzumaki.

Naruto entered the room and approached his mother's bed, carefully disarming a series of very volatile seal arrays he had set up to protect this room, and bent down to kiss her warm forehead.

"Hey, kaa-chan. Sorry I haven't visited for a few weeks. Things in Kiri are pretty hectic with the rebuilding we're doing." He said softly to her unconscious form, running a hand through her still-vibrant red hair.

He went through his routine of checking the seals he'd placed on her, recharging those that were running low on chakra. The most important of them were the stasis seals.

Stasis seals had been invented over a hundred years ago, and were used mostly by food traders to preserve their wares on long trips, and prevent decay. It did have some effect, especially on fragile foods like fruits and vegetables, but had the overall effect of "freezing time" – or rather, making it pass much more slowly for whatever was under the effect of the seal than it did for the rest of the world.

It had been the Uzumaki Clan that had realized its use in combat medicine, and developed several variants of the seal that could be used to place a grievously injured Shinobi into a temporary stasis, until they could be transported back to the field hospital where there were more to care for and treat their injuries.

Long term use, though, anything more than a few days, wreaked havoc on the bodies and chakra systems of those it was used on. Longer than a month, and most Shinobi would be dead. The Uzumaki, however, had found that the effects were not as serious on those with their Clan, as the effects occurred slowly enough that they could be matched and opposed by the natural healing abilities of those had the Uzumaki bloodline.

Naruto had found the long-term seals amongst the family scrolls, and applied them to Kushina a few months after his escape from Konoha. He had kept them in place ever since, after determining that her healing abilities were keeping up with the damaging effects of the seals.

In effect, her body had retained much of its muscle tone and muscle mass – one of the main problems that most long-term coma patients faced was having to recover their former strength when they awoke – and had hardly aged a day since she'd been placed under stasis. It felt somewhat odd when he thought about it, but now having recently turned 21 years old, her body was essentially only a few years older than his own.

Naruto glanced over at a workbench to the side of the bed, and fought down his frustration at the sight of his most recent failed attempt at reviving her. He'd tried so many things he'd lost count, but while the failures brought frustration, he never lost his certainty that he could bring her back somehow, and never dimmed his resolve to do so.

Once the seals were all fully powered and he'd ensured they were all working properly, he sat down on the bed next to her, and reached a hand up to gently stroke her cheek, looking down at her ever-beautiful face.

"I'm sorry it's taking so long, kaa-chan. When I ran away like I did, I was so naïve. I thought I'd have you cured and back to normal within a year. Now when you wake up, you'll hardly even recognize me. I hope I'm still making you proud, even if I'm not even proud of some of the things I've done to try to help you. Orochimaru…. Now that was my biggest mistake. I was still a stupid kid then."

"I've got a new lead, though. Some rumors of a restoration jutsu from some traveling doctor named Shinnō… I'll have to find him and hope he's the real thing." Naruto sighed, remembering the many leads he'd chased down that had turned out to be nothing more than people making claims to make themselves look important or special. And the many others that were legitimate, but simply didn't seem to work for Kushina's condition.

"It's that time again, kaa-chan. Kasumi and Karin would be turning twelve in a few days. I'll visit their graves like I always do, and leave a flower from me and you. And Minato-san's, too, of course. I know you loved him, and I realize now that I did too. He couldn't ever be my father, but he was my friend, and he still is who I strive to be like."

"I wish… I wish my sisters could at least have lived… I wish I could have raised them like you raised me, kaa-chan. I'm sorry I couldn't protect any of you," he whispered, squeezing her hand as a single tear slid down his cheek, and landed on her own.

He chuckled slightly. "Heh, look at me getting all weepy again – always do this time of year. You always told me I shouldn't lock away my emotions completely like some Shinobi do, so I guess I'm just listening to you even now."

Naruto sighed softly as Samehada rustled slightly on his back, sensing his grief, and her handle shifted around to pat him softly on the shoulder. "Thanks girl," he said softly, and then shifted his attention back to his mother. "I'll bring you back, kaa-chan," he said, repeating the promise he always told her each time he visited.

He paused slightly, and then leaned down to kiss her forehead once more. "This time, I know it. Something's going to change, but I don't know what. I'll be able to bring you back soon, I can feel it in my bones."

He stood slowly from the bed, and made his way out of the room, resetting the trap-seals as he went. As he reached the surface, and the bright afternoon sun beat down on him, his eyes and expression hardened into the emotionless mask he showed to his enemies. He turned in the direction of the Land of Frost, and set out through Uzushio's ruins. He had several days of travel, and a traitor to catch, and he wasn't going to let it keep him from visiting his sisters' and stepfather's memorials.

-oOo-

A/N: *Ducks rotten fruit* Please don't kill me, Kisame fans! He's one of my faves as well, but unfortunately he just had to go in this. Don't worry, as I mentioned earlier about flashbacks, we'll be seeing plenty of him in flashbacks in future chapters, and find out a bit more on how he and Naruto met and what happened with them to change things so drastically. I thought a Sempai-kōhai relationship (sort of like mentor/apprentice) fitted them the best, and again, more on that in the future.

I wavered between giving Naruto Samehada, or giving him Hiramekarei (the flounder-shaped sword), but I think Samehada will end up giving the best plot potential (both with Naruto's own use of it, and the exploration of the Naruto/Kisame friendship).

So… Naruto's a Swordsman of the Mist, his sisters are still in Konoha and being watched over by a certain someone ;), Kushina's body is still being kept in good shape by Naruto, and he's managed to even find a bit of a ragtag family for himself. And yes, Haku is a girl in this universe, I don't care what Kishimoto says (Damn you Kishi and your traps! *shakes fist*).

As far as Orochimaru goes in the first part of the chapter, Kishi doesn't exactly have a very coherent timeline, and lots of times things seem to contradict, so I'm not really sure when Orochimaru left. If you go by Yamato's age, you could assume he left around 20 years before the start of the anime/manga. But if you look at what other things were said, it makes it seem like he was still in the village when Sarutobi chose Minato over him (one of the things he was bitter about) for Fourth Hokage, so it seems like he left sometime after that (and given it was Sarutobi that confronted him and not Minato, it's likely it happened after the Kyūbi attack). So, I'm using my author's license and going with him not yet having defected at the time of the Kyūbi attack, but something that would happen sometime after Jiraiya and sarutobi's conversation here.

Next chapter, there'll be a decent amount of action as Naruto goes missing-nin hunting before his annual visit to his sisters' graves… where then finds out Konoha's dirty little secret. Until then, thanks for reading, and please leave your feedback!