No one is quite sure as to where Nightmare came from, what Nightmare was before his mutation, or even if he was mutated at all. He entered Xenon's service tens of thousands of years ago, when he was told to hunt down Toa Vundas. Toa Vundas was killed later, however, and Nightmare laid low for a long time.
About 80,000 years later, Nightmare was called back into service to hunt down another Toa, this one named MT. The reason Nightmare was asked to do this was because MT was something completely unheard of: A Toa of Xenon, yet he had retained his free will. Nightmare tried to hunt down MT, but was never caught up with the Toa, until a couple years later when MT re-emerged from hiding as a Toa of Light with Xenon powers. Nightmare confronted MT several times, but was never able to kill him, as MT always managed to slip away. Nightmare even went so far as to hunt MT down inside a Xenon Core, but he still couldn't kill the Toa, as MT's partner, a half Makuta half Toa mutation named Blackout, forced Nightmare to battle him, giving MT time to flee.
After several failures, Nightmare made his way to the House, and there he battled and easily defeated 4 Toa, and managed to steal Toa Levacius's weapon as well, but chose to leave the Toa lying there as he was unused to being shrunk to toy size in planet Earth's atmosphere. He then tracked MT down to Planet Mandex, and found him close by his own gunship. Deciding that fighting two Toa and a ship would probably be a waste of time, Nightmare showed MT Levacius's spear and told him that Levacius was being held captive in Nightmare's castle(which was a lie). Nightmare then returned to the top of his own castle on Planet Iranar, where he found Toa Tarakavarbiter and Levacius ready for a battle.