Kingdom Hearts: Chain of Memories takes place directly after the ending of the first game, Kingdom Hearts. Sora and his friends Donald, Goofy, and Jiminy Cricket are walking down a winding path when a mysterious man dressed in a black, hooded coat appears. He directs Sora towards a massive fortress called Castle Oblivion and then disappears. When the travelers enter, they find the mysterious figure again. When Sora and his companions attempt to engage the figure, they find that their abilities seem to have no effect. The figure explains that they forgot all of their abilities when they entered the castle. He continues by creating a deck of cards made from Sora's and his friends' memories, and tells them that everything they encounter in this castle will be based on their memories. The higher they go, the more memories they will lose in the process.
Sora is unaware that he is being watched by a mysterious group called the Organization. Marluxia, the lord of Castle Oblivion and the figure who lured Sora there, plans to control Sora with the memory-altering powers of a girl named Naminé and use her to overthrow the rest of the Organization. The Organization members Zexion and Lexaeus catch wind of this plot and observe it while the member of their circle, Vexen, decides to use a replica of Riku against Sora when Lexaeus sends him up to sabotage Marluxia's plan, agreeing to have the replica's memory reworked with Naminé's powers.
As Sora ascends the castle, he battles Larxene, a co-conspirator in Marluxia's plot. Afterwards, he appears to remember Naminé as an old friend of his. He learns that she is being held in the castle, and continues to ascend, clashing with the Riku replica who now believes himself to be the real Riku. After witnessing the death of Vexen and killing Larxene, Sora learns about his shifting memories and Marluxia's plans from Naminé; Axel, another Organization member who serves as a double agent, had allowed Naminé to meet Sora to foil Marluxia's plans. Sora forms an alliance with the Riku Replica—who discovers that his memory was also altered by Naminé—and they fight to the top of the castle and defeat Marluxia. Naminé then puts Sora and his friends into pod-like machines to help them regain the memories they lost in the castle, even though they would forget the events that transpired in the castle. Before they are put to sleep, Sora and Naminé promise to meet again as real friends once he wakes up, Sora firmly believing that his memories of her and the castle will remain in his heart despite being forgotten.
In the second story mode, Riku has been transported from the realm of darkness and fights his inner darkness as he battles upward from the basement levels of Castle Oblivion. Vexen fights Riku to obtain his data and creates the replica of him that lacks the original's fear of darkness, believing himself to be stronger. Ansem, who took over Riku's body in the previous game, attempts to regain control of Riku below, but is continually thwarted by King Mickey's support. On the way, Riku battles and defeats Lexaeus, only to be dragged into the realm of darkness. However, he is saved by King Mickey when Ansem nearly succeeds in taking Riku's body as his own. Seeing Riku of no use to them as Marluxia has been eliminated, Zexion attempts to dispose of him by tricking him in the Destiny Islands disguised as Sora. However, when Zexion drowns Riku in light, he is saved by Naminé disguised as Kairi. With the darkness in his control, Riku defeats Zexion. Arriving in Twilight Town, Riku meets DiZ, an enigmatic man interested in Riku who sends him to find Naminé. The Riku Replica, who now seeks to justify his existence, fights Riku in front of the mansion in Twilight Town, only to be destroyed by him. Riku learns from Naminé that what remains of Ansem lives in his heart. Riku chooses to face him and DiZ pulls Ansem from Riku's heart to battle. After defeating Ansem, Riku vows to utilize both his darkness and his light to protect what's important to him. He sets out with King Mickey as his companion.