The story begins with an immortal man named Kaim, in a decisive battle between the Magic Republic of Uhra and Khent, on the Highlands of Wohl. In the midst of the battle, the skies become an ominous pitch black and a giant meteor mysteriously appears over the battle field. The meteor rains molten lava from the heavens before crashing down on the field below it. All of the troops on either side of the conflict near the impact site are completely annihilated.
The Uhran council suspects a leak of magical energy from Grand Staff (a 'magic engine' under construction in the Sea of Baus) to be responsible for the meteor, and places its overseer -- the sorcerer Gongora -- under house arrest. Since he is immortal, Kaim was one of few survivors from the meteor's crater site, and thus summoned to the council. When asked precisely how he survived, Kaim confesses that he does not know. Gongora, who vouches for the man, states that he is under an immortality spell that he (Gongora) cast on him. Questioned about the secrets of the spell, Gongora explains that the spell is cursed, and that all those who hear about it die shortly thereafter. The council takes Gongora's word on the matter, and ask no further questions. The council, who have lost contact with the construction at Grand Staff, order Kaim to investigate, and return with a detailed report. The council unanimously vote to suspend construction of Grand Staff until Kaim returns, much to the dislike of Gongora, and furthermore place Gongora under house arrest and suspend him from the council. Kaim is ordered to take Seth, another immortal who survived the meteor, along with him. Gongora, who has a mysterious connection with Kaim, later orders him to take Jansen, a hired mercenary, with him to Grand Staff.
That night Kaim experiences a nightmare where he sees a young girl jump off of a cliff. It is hinted that these strange nightmares are fragments of his past.
Uhra has recently become a republic. Tolten is heir to the throne and would become King if Uhra was still a monarchy. Tolten is an honest and trusting, if naive, character. Although Tolten has agreed to Uhra being a republic, Gongora warns him that others may still resist. Later, Gongora storms into the prince's lair and tosses his soup on the floor, feeding the meal to a rat which is killed from inside by a plant-like creature that was residing in the soup. Gongora then burns the creature and the soup with a Flare spell. Tolten humbly thanks Gongora for saving his life. Gongora claims to be proud to help his majesty, however, later pays off the servant who prepared the soup in an obvious set up planned by the sorcerer.
The investigation of Grand Staff is interrupted by an impromptu assault from the army of Numara led by General Kakanas. Kaim, Seth, and Jansen are taken prisoner aboard the White Boa. While imprisoned, Kaim has another nightmare similar to the one before, this time showing Kaim and a woman weeping after the girl jumps, and a dark figure in the distance. Jansen uses a magical crystal, which erases the victim's memory and was given to him by Gongora, on a guard to escape their holding cell (even though he was ordered to use it on Kaim or Seth if their memories started to return). While escaping, Seth has a memory return to her, about the Queen of Numara, remembering that they were once friends. Their attempted escape fails, but they are set free once they reach Numara. Kakanas hopes that in freeing, and secretly following them, they will lead Numara to more information on Uhra and Grand Staff. Kakanas insists Numara prepare for war against Uhra, and begins to maintain war preparations, much to the discontent of Ming's wishes, who wishes to remain isolated.
Kaim, Seth, and Jansen then meet Cooke and Mack by a field of flowers called tenderflora, at the outskirts of Numara. After fending off soldiers who were bullying the children, they are invited to the children's home mama boy. Several memories return to Kaim when he meets the children's very ill mother, Lirum. Lirum turns out to be Kaim's daughter, now physically aged beyond Kaim. She was also the girl in Kaim's dream, and the woman from these dreams was revealed to be Sarah, Kaim's wife and Lirum's mother. Kaim also remembers that Gongora was the dark figure. Unfortunately, Lirum had been very sick for some time now, and was on her deathbed when Kaim arrives. Having seen her father one last time, Lirum passes away, entrusting her children to Kaim. Kaim realizes that Gongora is responsible for his lost memories, and that Sarah is also an immortal. With a portion of his memory regained, Kaim decides to head out in search of Sarah.
Back in Uhra, Chairman Roxian attacks Tolten, and Tolten defends himself by killing the chairman. Gongora arrives and convinces Tolten that they must claim Roxian's death was an accident, and that Tolten must accept his role as King. However, the Roxian that Tolten killed was really a monster summoned by Gongora, and the real Roxian was devoured by a snake under Gongora's control.
After Lirum's funeral, Mack wanders off to the Crimson Forest, where one may supposedly commune with the dead. The Crimson Forest is cursed from a war 500 years ago started by the Eastern Tribe. Mack is found possessed by the evil spirit of the forest. After the party saves Mack, a wind that is harsh at first but soon becomes gentle arrives and flowers begin to bloom all around. The children believe that the wind is a sign from their mother. Later, Mack is overwhelmed by a feeling of unease, and Seth explains that he has become affluent in the powers of the Eastern Tribe, as a result of being possessed by the spirits in the forest.
When they arrive back in Numara, they see a global announcement of Tolten's claim to the throne of Uhra, and that Gongora has been appointed as royal advisor. The announcement also shows Numara's army preparing for war against Uhra, seemingly from Jansen's point of view, causing the party to suspect that Jansen is a spy.. General Kakanas attacks the party, Kaim convinces Cooke & Mack to flee and the others willingly become imprisoned as spies in order to speak with Ming.
A Numaran sorcerer removes a Spy Eye from Jansen's right eye. Jansen claims to not have known about the spy eye. Even though the Numaran sorcerer validates Jansen's claim that he was unaware of the Spy Eye, Kakanas orders Kaim, Seth, and Jansen killed. However, Cooke & Mack return and cast a spell in which Kakanas and several soldiers are stripped to their underwear. In the confusion, an escape is made to Ming's bedroom. Kakanas catches up to them, but they escape by pretending to take Ming hostage (Ming herself aids the escape by mentioning a secret passage). Kakanas intercepts them once more with a tank, but is defeated. Ming, who turns out to know Cooke and Mack (they call her Aunt Ming, because she had been befriended their mother prior to the game). agrees to join the party, hoping to regain her lost memories.
They steal the Slantnose, a ship being prepared for Kakanas, just as its engine (which was once owned by Seth) is restored. Ming is updated on what they know so far; Kaim, Seth, herself, Sarah, and Gongora are immortals sent to this world to accomplish something very important (but because their memories have not fully returned they are unable to recall the exact nature of their quest). A one thousand year pact was agreed upon by the immortals, however, at the end of the thousand years Gongora betrayed the pact and the group. Since they are immortal and he cannot kill them he takes something very dear from each of them, in an attempt to break their wills, then he cast a spell on them to erase their memories.
With a part of their past unveiled the party decides to head back to Uhra and face Gongora. However, since their current ship is not strong enough to cross the ocean back to Uhra, they decide to head to Gohtza for aid. Gohtza is considered the primer nation in the fields of science and technology, thus the party feels confident that, with the help of the wise and benevolent king of Gohtza, they will find a ship that will transport them across the ocean.
The party arrives at Tosca, a small port town, and discover that the Black Cave (the path to Gohtza) is sealed. The innkeeper informs them that an old sorceress sealed it and would be the only one capable of unsealing it. They find the old sorceress, in Kaim's old residence. The old sorceress who turns out to be Sarah, driven mad by memories of losing Lirum at the Cliff, had returned to her old home to wallow in her despair, causing her to give in to her pained emotions. Though she was trapped by Gongora's spell, the kindness in her heart did not fade. Cooke and Mack revive Sarah by singing a family lullaby.
Sarah knows that Kaim is her husband from journals that she kept. Sarah joins the others and breaks the seal on the Black Cave. A dark power is sensed in the caves and is discovered to be coming from the ocean across Saman, a small merchant town. They take a small boat from Saman and head toward the power, however during the trip they are ambushed by mutated sea creatures, shortly afterwards a bright white light knocks everyone out. They awake at the Experimental Staff and meet up with Gongora. Gongora defeats them in battle, with Tolten coming across the scene once the party is defeated.. Gongora assures Tolten that the others were assassins that must have been dealt with.
Since vital components of Experimental Staff are ready to move to Grand Staff, Experimental Staff is demolished, with the other immortals, Jansen, and the children left behind to sink into darkness for eternity. However, a power awakes the children, which they again believe to be a sign from Lirum. The children awake the others and they escape to the ship as Experimental Staff sinks into the ocean.
The group heads back to Saman after a narrow escape at Experimental Staff, with their ship sinking just after they reach the harbor. Just when they are about to give up of hope of ever reaching Gohtza, they learn that the massive lighting caused by the fallout of Experimental Staff melted part of the glacier that was blocking the entrance to Ice Canyon. With the path clear the group makes their way through the Ice Canyon to reach Gohtza.
Once they arrive, the group learns that they aren't allowed to enter without proof of citizenship. Soon after, a mysterious figure drops a coin-like jewel near the group; Kaim and Sarah, who seem to recognize the coin, depart to follow him. Seeing the royal train arrive, the children take off to examine it. Seth, Jansen, and Ming head toward the royal palace. In order to speak with the king, Ming is forced to show proof of her royal bloodline; she shows the guards the royal crest on her chest to prove her identity. They are finally let into the throne room, after Seth and Jansen coerce the guards at the gate. However, the man sitting on the throne is only a placeholder for the real king.
The real king of Gohtza was the mysterious figure from earlier, and the coin he dropped was a memento that Kaim and Sarah gave him 50 years ago. At a private meeting with him in a Low Town apartment building, Kaim and Sarah discover that he has arranged a secret meeting with King Tolten in an final effort to prevent war, The king asks them to attend the meeting, and serve as his mediators. Kaim and Sarah warn him about Gongora's sinister plans to take over the world. They also confirm that the Ming is with them.
Meanwhile, an old woman tells the children about the Violet Aurora, a mysterious force that allows the living to communicate with the spirits of the departed. Mack and Cooke immediately see this as a chance to be with their mother one last time. Mack convinces Cooke to steal a train and head out to view the aurora. While the children take off in search of the Violet Aurora, the fake king informs Ming, Seth, and Jansen about the secret meeting. The three of them head out to the train and catch up with Kaim and Sarah. When they hear news that the children have stolen a train, to go in search of the Aurora; Kaim and Sarah immediately go after them. The rest of the group goes off to the meeting on the royal carriage.
At the meeting, Ming warns Tolten about Gongora and Grand Staff. Ming advises Tolten to destroy Grand Staff before another catastrophe like the one at Highlands of Wohl happens again. Tolten argues that Grand Staff is too important to be destroyed, and King Gohtza agrees. Gongora, who is back in Uhra, had placed a Spy Eye on Tolten, and uses a magical device to tell Tolten to agree to hand over plans of Grand Staff at Khent and announce an alliance with Gohtza. Tolten and King Gohtza plan a second Grand Staff to be built for Gohtza, despite Ming's protests.
Meanwhile, Gongora makes a public announcement to Uhra about the completion of Grand Staff. He also announces that King Tolten had secretly planned a meeting with King Gohtza to attempt to come to a compromise and thus avoid war. Gongora falsely claims that Gohztain officials reported that King Tolten fell ill and swiftly passed, but Uhran informants had discovered that they King had been set up and murdered. Gongora then announces that King Tolten, who foresaw his death, had left him in power.
He uses Grand Staff to send a meteor shower on the Gohtzan fleet stationed at Khent. He then summons a massive disc-shaped structure of ice that travels above Gohtza, freezing the castle, the city, and all those inside. Low Town then became the only inhabitable Gohtzan town. As the royal carriage is being frozen, King Gohtza orders a military response. An Uhran soldier casts a spell to warp Tolten back to Uhra, which Seth is knocked into during the chaos on the train. Ming releases her power to keep herself and Jansen from freezing. In doing so, her memories are released. She later recalls that Gongora had forced her to lock away her own memories in order to save her kingdom.
Meanwhile, an ice airship attacks the train that Kaim and Sarah have stolen to catch up to the children, and they jump to the children's train as their own is destroyed. They find the children, together, protected from freezing by a spell that Cooke had cast. An ice monster was immediately next to them, which Kaim and Sarah kill to save them. Sarah then uses her power to split the car in two. The children's half slows to a stop while the half with Kaim and Sarah aboard collides with and detonates the airship. Ming and Jansen set out on the train rails in search of the others and find the children. The children tell them what happened and they search for Kaim and Sarah.
Meanwhile, in Uhra, soldiers believe that Tolten is an impersonator, since they were told he was dead. Tolten and Seth see a broadcast of Gongora's initiation ceremony, where a sacrifice of criminals is to take place. Among the criminals is the great pirate Sed, Seth's son. However, before the criminals can be burned, the Gohtzan underground army attacks. Seth and Tolten use the attack to gain access to the Amphitheater in the Sky and save Sed. Sed leads them through the sewers, during which they see Grand Staff fly away. They find Sed's ship, the Nautilus, and escape also.
Seth uses a pendant she gave Ming to track her to the Burning Cavern. Ming, Jansen, Cooke and Mack were headed through the cave to find Kaim and Sarah, who was imprisoned by a magic ice monster. Upon beating it, the Nautilus appears, carrying Seth's group. With the entire party reunited, they set off to take down Gongora.
Seth explains to the others that Gongora is no longer in Uhra, but aboard Grand Staff. Sed suggests that they search an Ancient Temple of the Eastern Tribe, where there is said to be a magical stone that may amplify magic energy. Even though the party retrieves the magic stone to power the Nautilus, they still cannot penetrate the hypercurrents, due to large glaciers which formed around the base of Grand Staff, because of the high density of magic energy in the area. As the party approaches Numara, they witness the rebirth of the Arthrosaurus. An ancient dinosaur like beast, that was released by Gongora once Ming had regained her full memories. A pack of Arthrosauruses, storms toward Numara. The group is able to thwart their attack aboard the Nautilus. Ming suggests they return to Numara. Although Kakanas has taken over Numara, he unexpectedly welcomes her back. However, during nightfall, he attacks the palace. Suspecting this, the palace has already been evacuated, and the party defeats Kakanas. Ming asks her ladies in waiting to rule during their absence, and the party seek out Grand Staff aboard the White Boa.
The party arrives at Grand Staff, but fail to meet up with Gongora, who flies off in the upper half. The lower base sinks, and the party jumps off of it into the White Boa to escape. When a large beam of magical energy emerges from the ocean, the party realizes that Gongora intends to use Grand Staff to align the stars with the Tower of Mirrors, and then use Grand Staff to destroy the mirrors and sever the link between the normal and immortal worlds. They use the Nautilus to crash into and board the airborne Grand Staff. They finally catch up to Gongora, who proceeds to possess Jansen and manipulate him like a puppet. Grand Staff then collides with the Tower of Mirrors. Gongora releases Jansen and escapes to the Tower, and the party makes their way back to the Nautilus to escape.
The final confrontation takes place at the Tower of Mirrors. The light from the mirrors comes from the same world the immortals came from, making them mortal. Gongora is somehow able to absorb power from the light emitted. Sed, Jansen, Tolten and the children use their power to create a dark shield to block out the light. While doing so, the immortals battle and defeat Gongora; Seth strikes the final blow to knock him out. During the battle, the mortals had become trapped in their own shield, and begin to die. The weakened Gongora awakens and claims victory, since the only way to save the mortals is to destroy the mirrors. Seth sacrifices herself to push Gongora back through to their home world as the other immortals destroy the mirrors.
Later, Sarah writes a letter for Seth in her journal, writing about what has become of the rest of the party and the world in general. Sarah, Kaim and the children have moved to a farm. Sed takes them on the Nautilus to a wedding ceremony where King Tolten weds Jansen and Ming. The game's final scene occurs on the Northern Cape, where Kaim and Sarah watch over Cooke and Mack. As Sarah wonders aloud what's in store for the couple after their promise to raise the two to adulthood has been fulfilled, Kaim suggests that they can always "try for another millennium" - one which he hopes will be filled with happier memories than the last.