The story begins as Grovyle, the playable main character, and Dusknoir lay on the ground unconscious back in the future. After waking up, Grovyle realizes the future is still dark, but reassures himself that the player and partner simply have not set the Time Gears in place yet. He is then spotted by a Sableye, who runs away. Dusknoir wakes up as well, but his injuries prevent him from attacking Grovyle. Grovyle then decides to travel to Temporal Tower and confront Primal Dialga, to buy his friends some time. He heads out into the Barren Valley with Dusknoir in pursuit.
At the Barren Valley Clearing, Dusknoir and the Sableye catch up to Grovyle and are about to attack him when the Sableye start attacking Dusknoir as well. Puzzled by this new development, Dusknoir has no choice but to fight alongside Grovyle. After the Sableye are defeated, he muses over his situation while Grovyle starts to leave. Dusknoir then proposes that he and Grovyle team up temporarily, claiming his need to question his minions and Primal Dialga. Grovyle, though wary, accepts. At the end of the Dark Wasteland, Grovyle sneaks up on a Sableye using Dig, taking him to an isolated place to question him. The Sableye reveals that they are on Primal Dialga's new henchman orders, a "resourceful" Pokémon to be sent to the past in Dusknoir's stead, who has also ordered for Dusknoir's elimination. Enraged, Dusknoir starts attacking the Sableye, venting his frustration by delivering a powerful punch to the rock walls. Dusknoir decides to accompany Grovyle to Temporal Tower. Grovyle agrees, but is concerned about what will happen if Dusknoir decides to side with Primal Dialga and the new henchman.
Arriving at the Temporal Pinnacle, the duo discovers that nobody is there. Grovyle is confused: to send an agent back to the past, Dialga would need to be inactive for a long time to accumulate enough power to do so. However, Dusknoir recalls that he could also use the Passage of Time in Dusk Forest to do this. Grovyle suddenly realizes that this would mean that Celebi is in danger of being captured by Dialga, and rushes to Dusk Forest. In the Black Swamp, they are once again confronted by Sableye. After their defeat, they reveal that Dialga has taken Celebi to Frozen Island, a desolate island to the south. Dusknoir informs Grovyle that the only way to get there is to be transported by the Porygon in Spacial Cliffs. As they head there, Dusknoir notes that he has begun to regain his strength, which concerns Grovyle, especially after recalling Dusknoir's behavior at the Dark Wasteland.
At the end of the dungeon, Grovyle and Dusknoir find the Porygon, who proceed to warp them to Frozen Island. Here, they find a trio of Snorunt who proceed to play a prank on Grovyle. While angered, he and Dusknoir proceed into Dark Ice Mountain. At the Pinnacle, Grovyle is almost struck by a falling ice shard, but Dusknoir pushes Grovyle out of the way and takes the hit instead. Before he can recover, however, they are attacked by a group of four Glalie and one Mamoswine. After they are defeated, they hide in a crack in the ice to let Dusknoir rest. As they talk, Dusknoir asks Grovyle why is he so intent in changing the future while knowing he would disappear should he succeed. Grovyle replies by saying that even if he had not changed history, he would eventually cease to exist. He would have preferred to make his spirit shine in his short life than live a long, unaccomplished life, so that his actions would be remembered and live on. While Dusknoir thinks about these statements, the duo heads out to Icicle Forest.
Once there, they notice that they find another Snorunt, who confirms that Celebi and the Sableye went through there. Before it can say anything else, one of the icicles starts to sparkle violently. After this, Snorunt runs away, and Grovyle and Dusknoir proceed into the dungeon. At the end of it, they stumble upon the Spiritomb from earlier, who is holding Celebi hostage. At this point, Grovyle starts feeling very uneasy, and as he steps into the middle of four large ice pillars, a powerful electrical discharge comes out of them, shocking Grovyle. Suddenly, Dusknoir starts laughing madly, revealing it was all according to his plan. All this time, he was luring Grovyle to this place so that the electricity would "melt his spirit away". After that had happened, Dusknoir, as a Ghost type, would inhabit his empty body and travel to the past. Disguised as Grovyle, the player and partner would immediately trust him, giving Dusknoir the perfect chance to ruin the past once more, finally revealing Dialga's henchman's identity: Grovyle himself. Grovyle is shocked, as he cannot see how he would have informed the Sableye, but then realizes that Dusknoir must have woken up before him after they arrived in the future, which gave him the chance.
However, despite all this, Grovyle still trusts Dusknoir. Although Dusknoir had betrayed him, Grovyle could sense that, through the course of their adventure, Dusknoir's spirit had begun to reform. His siding with Primal Dialga simply came from a desire to not disappear. Grovyle declares that there is no happiness to be found in the dark future. Dusknoir begins to struggle with these feelings, while Grovyle directs the same statement to the Sableye. Soon, the electrical discharge becomes too much for Grovyle and he finally begins to fade away. Dusknoir saves him at the last second.
Everyone is shocked, but soon, Primal Dialga appears and starts attacking Dusknoir for his betrayal. The Sableye attack Dialga, but to no avail, as they are knocked back as well. Grovyle's strength has been completely drained away, and he is unable to do anything to help. Spiritomb then flees, freeing Celebi. It is at this point, however, that an aurora suddenly appears in the sky, and a wind starts blowing, showing that time has started to move once more. However, this drives Dialga completely berserk, acting solely on instinct and fleeing to Vast Ice Mountain. Dusknoir theorizes that his instinct has driven him to destroy the second Passage of Time located at the summit, an act with incalculable consequences. However, Grovyle knows that he is starting to vanish, so the group quickly make their way to the summit.
At the Pinnacle, Grovyle, Dusknoir, and Celebi finally confront Primal Dialga. Dawn is breaking, and Dialga seems to be affected by the flow of time. Suddenly, all four of them start to vanish, which prompts the final battle to begin. As Dialga is defeated, morning finally arrives, and one by one, they start to disappear, starting with Dialga. As Dusknoir is vanishing, he asks whether or not his spirit shone. Grovyle responds that it did, and finally content, Dusknoir vanishes. The sun rises, and Grovyle, with Celebi in his arms, watches the beautiful sight as they vanish together. The world of the future finally starts to move, as everything falls into place once more.
However, the trio soon awakens, realizing they have not disappeared, and neither have the other Pokémon. Dialga appears, restored to normal. He is eternally grateful to them, and starts to transform the world into a lush, verdant land. Dialga says their survival was the doing of a higher being. It is then that Grovyle, thoroughly overjoyed to be alive, starts sending a message on the wind to the player and partner, telling them they are safe, promising to rebuild the world.