AN: How's this for a blast to the past! A lot of you were bummed when this was abandoned, but now it is my hope that I can start and finish this one. I'm still working on Akuma no Senshi, but my mind cannot stay focused on that story right now; I've hit a wall. Don't worry, I only got about 7 chapters left.

Things to Note:

Some characters might be OC

Alternate Universe

Possible Character Death

Elders and Danzo for council, no civilians or clan heads

Mature Naruto

Strong Naruto

If any of these fall into the category in which you don't like, than I kindly ask that you refrain from reading this story. Thanks, and enjoy the rewrite!

Disclaimer: I do not own Naruto nor am I doing this for monetary gain, all rights go to their respective owners.

ITALICS – thinking

BOLD – demon speak

Arc One: Beginning of a Legend

Chapter One

A lone figure wandered the Elemental Nations in the search for his next destination. It had been years since he defected from his former home, but since then he has done jobs for some villages, killed missing-nin, among other tasks, all for the sake of making a living. The lone figure, who resembled a shark more than anything else, was none other than Kisame Hoshigaki.

Kisame didn't care where he wandered, why should he when he was an S-rank missing nin? Mostly everyone steered clear of him, but for those that thought otherwise in the hopes of making a quick buck or two quickly found out why he was called the Tailless Tailed Beast. Needless to say, those stupid enough to attack Kisame was as good as dead. However, there was one person whom Kisame always wondered about, one person who appeared from seemingly nowhere and offered him the chance to join an organization. As much as he wanted to join, a sudden coughing fit interrupted those thoughts which brought Kisame back to reality. He declined, but told the mysterious man in an orange spiral mask that he would still keep his mind open to the possibility.

That was over a week ago, and the mysterious man hadn't returned. Kisame didn't mind, however, as he had a new goal in mind seeming that his illness was getting worse. Instead of just minor coughing fits, they were more frequent but usually followed up with some blood.

"I swear Yagura had me poisoned or something happened on one of those damn suicide missions the bastard sent me on." Kisame grumbled to himself only to start coughing into his hand. "More blood…" The Swordsman's eyes softened upon the site. "…I need to find an apprentice and fast."

Samehada started to fidget and squeal which made Kisame realize that he hadn't killed anyone in two weeks; the sword was hungry for chakra. With a sigh, the shark like man stopped and turned towards Fire Country in the hopes of taking out a bandit camp or two. Little did he know, however, that his decision would lead to a legend being born.

Konoha – Hours Later

Hiruzen Sarutobi, the Sandaime Hokage, watched with a smile as his surrogate grandson slurped down his ramen with gusto. For him, seeing this brought back memories of Kushina Uzumaki, the kid's mother. His trip down memory lane, however, was broken by he sound of Naruto asking for another bowl.

"My, Naruto-kun, you sure you can handle another?" Teuchi asked with a smile as he took the third bowl away from the five, almost six, year old.

"Yep!" Naruto nodded which made Hiruzen let out a small chuckle.

"I think you've had enough, Naruto-kun." The Sandaime caringly said which made Naruto pout.

"But Ji-Ji, I'm still hungry."

Hiruzen palmed his face and sighed, "Where does it all go?" "Fine, Naruto-kun, but only one more OK?"

Naruto smiled and hugged his grandfather figure, "Thanks Ji-Ji!"

The Sandaime patted the boy's head and went to return to his food when he was interrupted by an ANBU.

"Yes, Boar?"

"Hokage-sama, your needed at the front-gates." Hiruzen quirked an eyebrow then motioned to whisper into his ear. "Apparently Kisame Hoshigaki wants to meet you in person, says he has a deal for you."

"Is he detained?" The Sandaime replied just as quietly.

"Hai, we have ANBU surrounding him, but oddly he hasn't put up a fight."

Confusion didn't even begin to describe what Hiruzen was feeling. He knew of Kisame, of his temperamental nature, so why was he so calm?

"Teuchi, would you mind looking over Naruto while I take this important call." The Sandaime said as he stood and placed some money on the counter to pay for the meals.

"Will do, Hokage-sama!" The head chef of Ichiraku's called back from the kitchen.

Hiruzen nodded then looked at Naruto, "Be on your best behavior for Teuchi, OK Naruto?"

"Gotcha, Ji-Ji!" Naruto said as his final bowl just came out. "Yes, more ramen!"

Hiruzen smiled then motioned to Boar whom put a hand on him to shunshin them both to the front gates.

Upon arriving, Hiruzen found the gate guards Kotetsu and Izumo looking just as confused as he was. There, just outside the village walls, was the Tailless Tailed Beast sitting in a meditative position with 40 ANBU standing at the ready around him. With a slow, but powerful and guarded gait, Hiruzen approached the missing-nin.

"It's not every day that a missing-nin of your caliber waltzes into Konoha alone, Kisame Hoshigaki." The missing-nin shifted which made the ANBU brandish their tanto. "Let the man stand and speak, ANBU, I may be old, but my skills haven't dulled."

The ANBU did as told and let Kisame stand who slowly pulled a scroll from the Kiri vest he was wearing. Being cautious, Hiruzen made a shadow clone to take the scroll into the nearby forest to check for any traps where it returned a minute later and shook his head before dispelling. Curious as to what was inside, Hiruzen opened the scroll and added chakra to it only to be surprised at what was now in his hands.

The Sword of the Thunder God.

Seeing this, Kisame smirked, "Perhaps now we can have a chat in your office, Hokage-san?"

The Sandaime sealed Tobirama's sword back up and put it in a pocket inside his Hokage garb before motioning for something else.

"You may have returned what is rightfully ours, but until I see the head of Aoi Rokusho, such a meeting will not take place."

Kisame sighed and pulled out another scroll which an ANBU looked over for traps with one of his shadow clones. Seeing none, the clone unsealed it which produced what Hiruzen was looking for. The blood on the severed neck was still fresh, and the cut was jagged and unclean which meant that Kisame had done the deed.

"Fine, you will get your meeting, but I must take your past actions into account." Hiruzen said as he turned around and headed towards the gates. "ANBU, I want him in the strongest chakra cuffs we have and escorted by at least thirty of you at all times, do I make myself clear?"

"Hai, Hokage-sama!" They responded.

"What about Samehada, Hokage-sama?" Boar asked knowing what the sword did.

"Think of this as a test of trust, Kisame-san." Hiruzen said as he turned and faced the now fully detained nin, his eyes boring into Kisame's own. "Keep your swords' tendencies at check, for if you don't, I won't hesitate to cut you down myself!"

"Hai, I understand, Hokage-san."

For the residents of Konoha, the sight of the Hokage and a massive team of ANBU escorting someone in chakra cuffs was enough for daily activities to pause for a moment before returning back to normal. Well, as normal as it could get seeming that this event would now be talked about for a long time to come; stories would be made, and rumors would be spread.

Hokage Office

Once inside the office, Hiruzen motioned for the ANBU to hide themselves, but leave ten around him for precautions sake. The door to the office was locked and security seals were in place so that nobody could get in or out. As Kisame was seated by Boar, the ex Kiri-nin couldn't help but look at the elder Hokage in front of him, a person that oozed this omnipotent aura despite his age, with a tinge of fear. He knew that one wrong word, or one wrong move would end it all; his dream crushed, never to be fulfilled.

"Now that we're situated, Kisame-san…" The Sandaime said as he sat down in his chair, only to grab his pipe off the desk and light it. "…please, do tell me why you're really here as I know it wasn't for some simple bounty."

"Although the money would be nice, you're assessment was correct." Kisame replied in his usual gruff tone. "In short, I want, no, need an apprentice so that I can pass on my skills to the next generation."

Hiruzen puffed on his pipe in thought before he replied, "And you thought to start your search here because Samehada picked up a large source of chakra correct?"

Kisame nodded just as the sword in question let out a squeal which put some of the ANBU on guard but Hiruzen motioned them to stand down.

"Hai, Hokage-san, but Samehada just informed me that the chakra in question was yours."

Kisame sighed and was about to talk when a sudden coughing fit came over him which ceased after thirty seconds; blood was now on the wooden floor.

"ANBU, fetch a medic for Kisame-san here, the last thing I want for him is to die while we negotiate."

"NO!" Kisame interrupted just as the ANBU was to leave. "I may be ill, but I refuse such treatment as my sins are too heavy."

"Compassion, Kisame?" The Sandaime smirked. "Now there's something I thought would never come out of the Tailless Tailed Beast."

"Bite me!" The man in question harshly quipped.

"And just like that, it's gone." Hiruzen amusedly thought before getting back on topic. "You are correct that I am the only person in Konoha at this moment with a large amount of chakra, sans my old friend Danzo, but I believe there is another person with just as much potential."

"Hokage-sama!" Boar yelled as he didn't like where this was going. "Not that I don't trust your leadership, but to let such a dangerous criminal train THAT boy?"

"Your concern is duly noted, Boar." Hiruzen smiled as he looked at Kisame, "But I judge a man's character not only on his past actions, but of his present ones as well. As of now, Kisame seems to be a trustworthy individual, but to be certain I would like to ask one thing."

"Name it, Hokage-san, I'd do anything to see my dream be accomplished before I pass from this world." Kisame pleaded.

"I want you to undergo a series of sessions down at T & I, no doubt you know who these people are." Kisame nodded as their names were renowned in the Elemental Nations. "Good, I await the reports Inoichi, Ibiki, and Anko will give me, from there I will pass judgement."

Kisame was helped up just as the seals went down and from there he was shunshined to T & I. Once gone, Hiruzen leaned back in his chair with a sigh as he thought about everything Naruto has gone through so far and how this new situation would play into it. Although the civilians never harmed Naruto physically, their stares and dismissals from stores was enough to harm mentally. Although he tried to hide it with a happy front, Hiruzen saw through it.

Although he had the Sandaime and the Ichiraku's, a semblance of family, Naruto wanted a true father figure. One that would be there for him night and day, one that wasn't burdened down with the duties of Hokage, and one that would gladly teach him the skills he needed to live in this harsh world. Now, Hiruzen and the Ichiraku's did teach him to read and write among some other things, but as for shinobi training; that was a different story. For Hiruzen, it was difficult for him to do so as some might see that as favoritism and demand that if Naruto got training, why not them?

The whole political situation was a headache, one that Hiruzen wanted gone. However, the Sandaime knew that if things worked out with Kisame, than perhaps two people's dreams could become true.

Following Morning – Hokage's Office

Shortly after returning from Naruto's apartment to see if his surrogate grandson was OK, Hiruzen returned to his office to do the usual paperwork for the day. As he walked, he couldn't help but hear the civilians chatter on about Kisame, or rather the blue shark man as they called him. Although it made the Hokage smirk at the nickname, he knew that the elders and Danzo would be in his office at any moment. And sure enough, just as he went to start paperwork, a knock was heard at the door.

"Come in Danzo, Koharu, Homura, the door's open." Once they were in, the door was closed and security seals activated. "Now, what can I do for you today?"

"You know damn well, Hokage-sama." Koharu replied rather bitterly. "In fact, the whole village has endlessly gone on and on about this blue shark man whom I can only deduce is Kisame Hoshikagi."

Hiruzen calmly lit his pipe and puffed on it a few times before he looked Koharu in the eyes.

"And you would like me to what, exactly?" He rhetorically asked. "Execute him for his past crimes, or just for stepping foot in Konoha and willingly giving up? Perhaps give him back to Kiri where they will gladly execute him there? The fact of the matter is, we won't do either as a dying man deserves to live out his final wish."

"And just like that, you let a traitor, a criminal into our village?" Danzo narrowed his remaining eye in disgust. "I always knew you were soft, Hiruzen, perhaps you aren't fit to lead anymore."

"I am anything but soft, Danzo, and you know damn well that I know about your still existing Root." Hiruzen smirked as he puffed on his pipe a few times. "But if you want me to return to the God of Shinobi, then by all means, let me contact the Fire Daimyo and inform him of your treasonous acts."

That shut Danzo up, but the Sandaime wasn't done as he looked at the two elders.

"In fact, I've gotten many complaints about the academy recently." Hiruzen looked around his desk and found the massive folder he was looking for. "This folder not only contains complaints from the last two years, but also reports of every genin whom has died as a result of the lackluster curriculum."

Danzo and the Elders were sweating and Hiruzen knew it which made the elder Hokage grin even more.

"As you can tell, I'm far from the soft, caring, Hokage or friend, you make me out to be. They say the enemy of my enemy is my friend and well what do you know." Hiruzen slammed the area with killing intent which Danzo, Koharu, and Homura hadn't felt in years. "I find that you three try to circumvent my authority in the hopes of boosting troop counts, only to fail in realizing why our academy was set up the way it was!

"H-Hokage-sama…we only did what we felt was best for the village." Koharu stuttered out, but got a nasty glare in return.

"And in turn, you have weakened the village the Shodai, our mentor, built!" Hiruzen, in a fit of anger crushed the pipe in his hands. "You're fired, all of you! Jiraiya and Tsunade will be returning and I will be notifying the Fire Daiymo of your actions." The Sandaime turned in his chair so that he was looking out the window. "ANBU, you know what to do."

Just as the seals went down, and the ANBU took the council to a holding cell, the secretary cautiously knocked on the door and cracked it open.

"Hokage-sama?"

"Yes, Megumi?"

"The reports from T & I have arrived."

"That quick?" Hiruzen turned to face the door only to receive a nod then a folder to be placed on his desk. "Thank you, you're dismissed."

Once the door was closed, the Sarutobi started to meticulously go through the files he was given and, to his utmost surprise, not one torture technique had to be used. Kisame simply spilled, but what he did didn't disappoint. In the years since he left Kiri, Kisame had done jobs for other main villages, mainly Kumo and Iwa, and had gotten a good layout of the place as well as some of their guard rotations and how security was run. Knowing that was years ago, Hiruzen took this information with a grain of salt, but knew that Jiraiya would fill in the rest once he returned. However, out of all the reports, one prominently stood out; the report of a strange man in an orange spiral mask. Hiruzen knew that Jiraiya was tracking something which was why he had been away for so long, and he had a sneaking suspicion that this mysterious man was the key to it all. Such suspicions, however, usually got you killed on the battlefield, something Hiruzen took to heart after living through all three Shinobi Wars.

"Heya, Sensei!" Jiraiya introduced himself in a puff of smoke which made Hiruzen jump from his seat, and papers to go everywhere. "Um…oops, heh heh."

"Dear Kami, Jiraiya how many times have I told you not to do that!?" The Sandaime lectured as he calmed his old heart.

"Plenty, but I'm not here for reminisce, quite the opposite I'm afraid."

"Does it deal with a man in an orange spiral mask?"

"No…" The Toad sage slowly replied as he looked at his Sensei with a raised eyebrow. "…I came to inform you that a new hidden village recently popped up in Rice Country. Apparently calls itself Hidden Sound, though I don't know who's running it." Jiraiya let out a small smile. "I was actually wondering if you wanted me to take an in-depth look."

Hiruzen shook his head, "I'm not authorizing such a mission as you will be stationed here for now on along with Tsunade."

"You cleaned house, didn't you." The Toad sage let out a groan. "And you want Tsunade-hime and I to become advisors?"

Hiruzen nodded as he handed his student the folder of reports he was given, "And that's not all, it finally looks like your godson will get the father figure he's always wanted, with you by his side."

It took a couple minutes to leaf through the reports, but once done he looked at his Sensei with wide eyes.

"You're an insane old man, you know that Sensei."

"Quite, and better yet, tomorrow is Naruto-kun's birthday." Hiruzen let out a happy sigh. "And what a birthday that will be."

Following Day – October 10

For Hiruzen, the past two days have been a whirlwind of excitement and headache. He was glad that he finally ousted his friends, albeit the term being used loosely, but herein the problem lied; what to do with them. He could have them executed for what they had done thanks to the investigation he issued on them months before handing down his verdict, but Hiruzen couldn't see himself issuing such a decree. Luckily for him, he sent a letter to the Fire Daiymo describing the situation, only to get one back last night saying that he would arrive later today to discuss details.

Another headache was Tsunade whom Jiraiya was sent to find. Hiruzen didn't know how long this would take, but he informed Jiraiya that if they met to tell her that she would have her gambling debts payed off and her medic program fully funded.

Amid these headaches was excitement, not only because Kisame spilled everything, but also because Naruto would get the biggest birthday gift to date. That is, if Kisame accepted and if Samehada didn't have a problem with Naruto touching it.

"Hokage-sama, Kisame is here to see you." Boar said as he appeared in the office via shunshin.

"Very well, send him in." Hiruzen replied. "Oh, and would you fetch Naruto please, he should be about done at Ichiraku's."

"Hai, Hokage-sama!" Boar saluted and left in a swirl of leaves.

As Kisame entered, he was still being escorted by ANBU and the chakra cuffs were still on him. As another trust exercise, Hiruzen had these removed but told the ANBU to stay vigilante as he didn't trust Kisame fully yet. By this time, Naruto arrived with Boar and said hello to his grandfatherly figure before noticing the scary looking man surrounded by ANBU. In fact, the way Kisame's eyes were made Naruto feel like he was being glared at by the villagers so, in fright, he hid behind Hiruzen's chair.

"Make the scary man go away, Ji-Ji." Naruto said as he took a peek only to quickly hide himself again.

"I'm afraid I can't do that, Naruto-kun, but if it makes you feel better, you can stay near me for the time being." Naruto nodded which made Hiruzen smile, though it was erased thanks to Kisame's next remark.

"This is the brat that you said had potential?" Kisame barked out a short laugh. "Ha, please, this brat hasn't even unlocked his chakra yet! Jokes over, Hokage-san, where's the real one at?"

"I assure you, Kisame-san, that this is indeed the boy." The Sandaime replied. "Go on Naruto-kun, introduce yourself."

Naruto gulped as he took a couple steps forward, but he still couldn't look into the man's eyes.

"Hi…m-my name's N-Naruto Uzumaki."

Naruto couldn't say anymore and quickly hid behind the seat again which made the Hokage sigh. He hoped that if Kisame accepted that he would help his surrogate grandson with his social interaction problem.

"Did I just hear that correctly, did he say Uzumaki?" Hiruzen nodded which made Kisame smirk. "Ah, now I see why you said this kid has potential, the Uzumaki were known for their large chakra pools."

The Tailless Tailed Beast paused as he looked at the boy then the picture of the Yondaime. Although Naruto was young, some resemblance was still there. Seeing this, the Sandaime gave Kisame a look which shut him up.

"So, he still doesn't trust me. Can't blame the guy, honestly." Kisame thought then looked at Naruto who decided to take a peek again. "And his shy nature only further solidifies my assumptions, but for now I will hold my tongue."

"Tread carefully with what you've deduced, Kisame-san, as those are S-rank secrets punishable by death."

Kisame nodded, "Now that the brat is here, what's next?"

"Although his chakra isn't unlocked yet, I still want to make sure if Samehada accepts Naruto or not."

The shark man grinned and took the sword off his back and placed it on the floor, but instead of staying like he and everyone else thought, it started to crawl its way towards Naruto. For the six year old, he was frightened, yes, but also intrigued. As the sword got closer, Naruto bent down to get a better look when Samehada suddenly leapt into his lap and started to squeal and lick Naruto's face. This was new for both Kisame and Hiruzen as they knew Naruto's chakra hadn't been awoken yet, but for Samehada to do this, it meant that some chakra was present.

"That's a first." Kisame was dumbfounded by the scene. "Perhaps Naruto's chakra pool is so large, it leaks out every now and again?"

"A possibility, but we won't know for sure until Naruto unlocks his chakra." Hiruzen said as Naruto started to laugh and try to pull Samehada away. "So, while my surrogate grandson is being entertained, I have one final test of trust for you."

"Name it?"

Just as Hiruzen looked for the adoption papers, Kisame had one of his coughing fits which made Samehada return to his master. For Naruto, he pouted that his source of fun was gone. The Hokage was worried about Kisame's health, but the man wiped the blood away and motioned that he was fine.

"Kisame Hoshikage, former member of the Seven Swordsman of the Mist, and S-rank missing nin, for your final test of trust, you are to adopt, and place, Naruto Uzumaki in your care as well as train him in the hopes that you can pass on your legacy." Kisame and Naruto were now paying full attention. "Furthermore, as stated on this affidavit in which you will sign and date with your own blood, you will also be under strict probation for the period of one full year or until I deem otherwise. Under this probation, you will be under ANBU watch and are expected to send monthly reports on Naruto-kun's progress to my desk every Monday morning. Failure to uphold this contract will result in immediate execution by decree of the Sandaime Hokage. If any of that wasn't clear, speak now or forever hold your peace."

"I understand fully, Hokage-san, and accept the length of probation you have stated." Kisame was at full attention, Samehada now placed back where it belonged.

Hiruzen nodded and presented the affidavit where Kisame bit his thumb and started to fill out where the Sandaime instructed. After another scan of the document, The Sandaime nodded in approval and signed his name at the bottom, but before it was deemed legal, the ANBU who escorted Kisame in signed as witnesses to the act. With a smile on his face, Hiruzen stood from his seat and helped Naruto walk up to Kisame where the two looked at each other. Sensing the kid's fear, the ex-Swordsman bent to Naruto's level and held out his right hand with a smile.

"C'mon kid, say hello to your new father."

That last word resonated in Naruto's mind and, for a reason unknown, he suddenly ran up and hugged what he thought was the scariest man in the world. For Kisame, however, he couldn't help but shed some tears of joy knowing that one of his dreams, a secret one known only to him, was now fulfilled. The Tailless Tailed Beast finally got the chance to experience what it was like to raise a son.