Author's Notes: So. Yeah, here is a story I'm writing. This is what I wrote during that week when I didn't write a chapter of Going My Way. Okay let's say things right off the bat right here and now.

1. This is both a time travel and an alternate universe fic.
2. The pairing here is undecided for the moment.
3. Naruto will have a kekkei genkai of sorts.
4. He will be powerful, but not godlike. He can still lose fights.

Now that those are out of the way. Here's the prologue to: Upon The Stars.

Disclaimer: I do not own Naruto.

Deep beneath the soil of the Elemental Nations laid a temple, one long forgotten by those the people of the land. It's pristine beauty was now lost to the sands of time. Moss and dust covered the area. The once high stone walls crumbling due to the passage of time. Vines crawled up the walls, while several weeds and grasses spread around the floor. The main chamber of the building was largest room in the temple. It was circular in shape and was the least touched by the decaying effects of time that had been wrought on the entire temple. Inside the room were nine gargantuan statues of beasts, all with varying numbers of tails. On the far side of the wall was a tenth statue, one that is not of a beast but a man. It was the smallest statue there, but if one were to look closely the nine beasts seemed to be looking at the man making it the most important.

In the middle of a the room was a blade, rusted over due to the oxidation of the air and the countless years of disuse. The sword was pierced into a large stone slab that shined in the cracks from the roof, where light seemed to filter in. The blade, even though rusted, was blue in coloration along with some orange on the sides. It was buried almost hilt deep, that one could not see how long the blade truly was. The guard on the blade was in the shape of a four pointed star, not unlike that of a shuriken and the handle was long enough to show that it could be wielded with either one hand or two.

There was a person standing in front of the blade with their hand stretched outward. The man stood at about 5'9" with chin length spiked hair. He had blue eyes, that seemed to have lost the shine in them, having lost their innocence and the happiness in them. There were three whisker marks on each cheek. He was dressed in an orange and black jumpsuit, but it looked like it had been through hell and back. There were many rips and cuts on the clothing. Blood had dried around some of the cuts, and several burn patches here and there. This was Naruto Uzumaki, a seventeen year old ninja of Konohagakure, the Village Hidden in the Leaves.

Or what used to be of Konohagakure at least.

It was year after the Fourth Ninja War. Many of the ninja that were fighting had lost their lives for the sake of protecting himself and another container of the bijuu, the Tailed Beasts, Killer B. They had won the war. They had beaten back Madara, the Zetsu army and the zombie troop. They had managed to save the world from meeting with a terrible fate of coming under the spell of Madara Uchiha, or the rather the person known as Tobi. However this victory came with a price. They had managed to save the world but the the Gedo Mazo, the structure that imprisoned the bijuu, had exploded. It spread the poisoning chakra of the bijuus into the sky, tainting the land and the sea. The people that survived the explosion were either poisoned by the amount of bijuu chakra in the air, or were forced to live underground waiting for the time that they would be able to once again go to the surface. It was a struggle for them to survive day to day life.

The reason why Naruto Uzumaki was here, was for one reason and one reason alone: the blade in the stone. Legend stated that it was called the Mugen no Ken, or the Blade of Infinity. In several scrolls that Naruto had found a few months after the war about the bijuu and the Rikudou Sennin, the Sage of Six Paths, there was some that talked about this blade. Rumors had stated that it was a long lost blade of the legendary Sage had used to battle the Juubi, the Ten Tailed Beast, before he used his legendary tools. Some scrolls said it was made out of a rock that came from the heavens. Others said that it had rather odd properties most swords would not have, but those were not the reasons Naruto went for the blade. The reason he went for the blade was one legend he read that he wanted, no, hoped is true: the blade had the power to change the world.

He wanted to change the world, to change just one thing in the world. To erase Madara from history. If he was never there to begin with all the world would have not gone through with this genocide and this destruction. "Although if he wasn't born, I wouldn't have met with Sasuke," Naruto stated with a bit of humor. "I guess he was useful for something after all." The blond then shook his head. "Enough thinking about the past. I need to go towards the future."

"Naruto, are you sure about this?" a voice deep within the confines of Naruto's head questioned the blond. The voice deep inside his head was the bijuu called the Kyuubi no Yoko, the Nine Tailed Demon Fox. It was not until the previous year he learned that the fox had a name, as well as became friends with one another. They had became close partners, ones who would could rely on each other. So now Naruto found himself deep within the recesses of his mind. His mindscape seemed to take the form of a sewer. There were pipes everywhere, along with shallow water and cracked walls. On the far side of the wall was a large cage, with the doors opened up. Within the cage was a large orange fox, with nine waving tails. It's red eyes were trained on Naruto.

"Kurama…" Naruto muttered. "I am sure about this."

"Of course you are. You aren't going to want to change your mind about this aren't you?"

"I'm not. With the way things are going right now, the human population won't even last a few more months let alone years." Naruto ran a hand through his hair. "If I can change the past with whatever power this blade possess, I'm going to take it no matter what."

"The consequences can be severe. We don't know what can happen if you do that, there are so many variables that we cannot account for that anything can happen."

"I know that, I know that." The blond began to pace. "Sadly this is the only option left. I've taken into consideration everything, All the things I've done to help the people out during the incident have come up with nothing. I tried using your chakra to counteract the effects of the chakra in the air, I tried asking several summons, hell I even tried using nature chakra. All of those came up with nothing." The blond sighed. "I can't let the people continue living like this, not after my failure."

"Is this really about them or about your failure Naruto?" When the blond didn't respond immediately, the fox knew what his partner was going through, survivor's guilt. The fox knew Naruto would do anything in his power if it meant being able give the world a shot at being better. "You are that desperate huh?"

"Very desperate."

"Well, there's not much I can do to stop you now can I?" The fox then smirked at the blond. "I guess I'll say this now since there may be a chance I won't be able to in the future. I'm glad we were partners, even if it was only a year. You made life more bearable and showed that there are people who really do care about bijuu.

"Ah don't get all soft on me now Kurama!" Naruto chuckled as he scratched the back of his head. "If it weren't for you I'd be dead over five times already." The human then looked at the fox for one last time and raised his fist towards him. Kurama gently tapped Naruto's fist with his own. That was when Naruto left his mind.

Upon opening his eyes one more, Naruto saw that he was still in the temple, still standing in front of the blade. Taking a deep breath, he reached out towards it. "It's now or never I guess." As he went to grab the handle, the stone that the blade was stabbed into began to shine. Naruto was rather surprised when that happened and was even more so when words appeared before him.

TO THOSE WHO TRY TO CLAIM THIS BLADE, BE WARNED. THE MOMENT YOU TRY, YOU MUST SUCCEED. FAILURE AND GIVING UP WILL LEAD TO PERIL. ONCE YOU TOUCH THIS BLADE, YOU MUST NEVER LET GO UNTIL IT IS FREE OF THE STONE.

"So I have to do this no matter what huh?" Shaking his head, Naruto grabbed the handle with both hands. "Here goes nothing then." Naruto tugged at the blade and it didn't budge at all. This caused him to frown. Pouring his chakra into his arms, he strengthened himself and pulled again only the blade hadn't budged at all. He kept trying over and over again. Slowly after a few minutes of pulling on the handle with no progress he grimaced. Without taking his hands off the blade, he closed his eyes and began to meditate. Slowly he felt power surging through him. Orange coloration appeared around his eyes and his own irises become not unlike that of a frog or a toad. Having turned on sage mode, Naruto tried to pull the sword out again, but yet it did not budge.

"Oh come on! Even with the power boost of sage mode you won't move a bit?" Naruto pulled even harder and yet, the blade would not budge. "Kurama help me out here!" Turning off sage mode, Naruto's bode was enveloped in a golden coat of chakra, and looked to be set a blaze. Two demonic looking arms appeared from his back and started to tug at the sword as well. Sadly it still wouldn't budge. So he kept pulling and pulling and still nothing was happening with the sword.

"Naruto! Stop pulling!" Kurama shouted from within his head.

"What why?" Naruto stopped tugging, but didn't let go of it.

"Don't you see what's happening to your body?" Naruto looked down at his arms and saw steam coming up from them. He knew what that meant. He had wounds and they were being healed. Inspecting one hand closely, he noticed that there were several deep cuts on his arms as well as on other parts of his body. "It seems as if the blade is trying to kill you while you tug at it."

"Damn." Naruto tested it out by pulling on the sword again. As he did, a long cut appeared on his right arm. "So pulling won't work on this thing. If that won't work then I might as well break this stone then." Two demonic arms appeared again and they both created two spiraling orbs of chakra each. The spheres started to get larger and larger until they were both the size of basketballs. "Oodama Rasenrengan!" Slamming his techniques into the stone, he waited for the small explosion but was surprised to see none. Instead, the stone was absorbing the energy, however when Naruto tugged at the blade again, it moved upward a five inches.

"Well, it seems like I found the way to get the sword." Naruto started to feed more and more chakra into the stone and the sword kept going coming from out of the stone with the help from Kurama. Bit by bit the blade came out, but Naruto was already feeling the strain on his own chakra reserves. "Kurama how much chakra do you still have?"

"This thing stone is one hungry piece of rock," the fox grunted. "I'm using up so much chakra right now. I probably used enough to fire one Bijuu Dama." That made the blond grunt in displeasure. This thing was taking way too much power. Naruto was continuously pouring energy into the stone, but unlike the beginning he was barely able to pull the thing out by a few more inches, at most it was out about a foot and a half.

"Well, let's keep going. I think this is the only way to take out the blade." Increasing their output, Naruto kept on tugging at the blade as the chakra was absorbed. It would be half an hour later when Naruto was able to pull out the sword from the stone, while pouring out so much energy from his body. Not only was he close to chakra exhaustion, but apparently the Kyuubi was as well. The good thing was their efforts were not in vain. In Naruto's hand was a three foot blade double sided blade. It was rusted over, but he could see specks of orange and blue on the blade itself. There were several insignias, probably seals, on it that stood out clearly even after all this time.

"No wonder no body has been able to pull that thing out, if anyone has tried at all," Kurama muttered from inside the boy's head. "That stone is a chakra hungry thing that even I'm exhausted. Nothing short of a jinchuuriki would be able to take that blade out."

"That's true. That and something around the blade is trying to cut you up while you do this." Naruto then looked at the blade. "Mugen no Ken, a sword with the power to change the world," he mumbled. "In legends it said it can take up the form of various other weapons with different abilities. It was also said that it would give the person an unbelievable ability." The blond's eyes roamed the blade until it landed on a seal on the guard of the sword. The array was written in tiny script but it was written around one big character, the kanji for 'world.' "So this is it partner. This may be the last we here of each other."

"It's been one hell of a run brat. Remember me, even if the world changes."

"I will." After that, Naruto raised his hand to his mouth and bit his thumb. Raising the bloodied digit to the seal, he smeared it across and focused chakra into it. He expected a big light show of sorts and he got that. What he didn't expect though was the pain, the excruciating amount of pain. It felt as if his body being torn limb from limb. His eyes were burning, his ears were ringing, hell he could even taste blood on his tongue. He could feel all his old wounds opening up one by one.

Just as this was happening, he slowly started loosing his senses. First he couldn't smell the blood on his body, then he couldn't taste it on his tongue. Soon he couldn't hear his own screams, then all was lost in the darkness of the abyss. Shortly after that he couldn't even feel his own pain. His lost thoughts to himself before blacking out were…"Was this what death feels like?"

If one were watching this event unfold, they would have seen it all happen in under a minute. They would have just seen a column of blue light descending from the sky engulfing the boy. They would hear out a loud yelp then it was over. When the light disappeared, any traces of Naruto was gone save for a hitai-ate (forehead protector).

Naruto slowly opened his eyes as he he woke up. His head hurt a lot. Trying to sit up he felt a pain shoot through his body. "Ugh...why does it feel like obaa-chan and Sakura decided to play volleyball with my head…" he mumbled. He tried to move again but felt an the pain again, but luckily it was subsiding. "Kurama, tell me what's wrong with my body please."

He got no answer. The blond frowned.

"Kurama?"

Again nothing. Reaching down he lifted up his shirt and found that there was no seal on his stomach. "Damn," Naruto cursed under his breath. His partner had been right. That was also when he saw something wrong with his body. "Where the hell are all my muscles?" Standing up, although struggling to do so, Naruto saw that his clothes were a few times larger than himself. His hands were smaller, as well as everything else. "Oh you have got to be kidding me. I need to find a mirror." Looking around he saw that he was still in the temple. Deciding it was best to leave along with the blade, seeing as it was his now, he started walking towards the door. As he did, he noticed that the blade was missing. "Oh don't tell me I lost that too."

He threw out his right hand and was surprised when the blade appeared in it. Seeing that the blade was now about the size of his body, Naruto was thrown forward and tripped onto the stone floor. Groaning, he sat up after the mishap and examined the blade. He had to raise an eyebrow when he saw the differences. There was no rust, no wear and it shined like it was newly made. The edges of the blade were orange, neon orange, and the center of it was a rich navy blue. The words scrawled onto the blade itself were in red. The wrapping for the guard was a fresh white and the golden guard sparkled in the light.

At first the things written upon the blade were the numbers one through twelve, but they had changed when some of his chakra entered the blade. Upon closer inspection, the new words written on the blade were odd to him. They seemed to have nothing in common. In order they were: scorpion, scales, maiden, lion, crab, twins, bull, ram, fishes, water-bearer, goat and archer. "The heck is that supposed to mean?" He tried to swipe some blood over the seals, but they wouldn't work. Then looking at the star shaped guard, he saw four more words: fire, air, earth, water. "Well, that is odd. Now how do I make this go away?" A cyan light engulfed the blade for a second and it flashed out.

"I am going to have to see what's up here." Making his way out of the temple and standing outside of it, he found himself in a cave. Walking out of the cave took about two hours, even thought it was just a straight path with not many obstacles in the way. As he reached the mouth of the cave he finally remembered something that slipped his mind. "How did the blade change the world? It never asked me for what I wanted or anything?" Cursing under his breath, Naruto knew he had to investigate but first he had to find what was different about himself. He walked towards the east, where he remembered there was a river that was contaminated by the volatile chakra.

As he made his way through, he noticed the changes already in the world around him. There was life there. The area wasn't a desolate wasteland anymore. Trees were all around him, animals were moving about and the sky was no longer a deep burning red, but the calming blue of times before the the catastrophic end of the war. "Well one thing is for sure," he said to himself, "the effects of the battle between the masked man and myself have not occurred."

When he finally reached the river, he knelt down by the river bed and took a drink of water. After that he took a good look at himself and was not as shocked as he was when he saw his reflection. He looked like he was six again. "I probably am given the circumstances that anything could have happened," he mumbled aloud to himself. He mostly looked the same when he was that young, same amount of baby fat, same build, same everything. Well almost. His hair was still it sun kissed blond but there were also some red at the tips of his hair. His eyes that were blue were now grey and itched for some reason.

Standing up he faced east once more and headed forward; his destination was Konoha. He wanted to know what had changed in this world seeing as that seal must have done something. "Let's see what's different here."

Leave me a review please.