Sora, Donald and Goofy finished they're last adventure, now they need to find the King and Riku. When they are sleeping, Sora wakes up and begins walking around. Suddenly he sees a man in a black coat, whose tell him "To find what you seek, you will loose what you hold dear.", Sora wonder what he means... Suddenly he sees a castle, and wakes up his friends, and they go in. Inside they see another man, in a black coat. This man gives Sora a card, that will open a door to another world. Let the adventure begin.
|This section contains spoilers! Content within this section may reveal significant parts of a game(s) story.|
CoM begins right at the ending of Kingdom Hearts, where Sora, Donald and Goofy have left Kingdom Hearts (place) and are walking down a grassy trail, in the crevasse between dark and light. Half of the game is from Sora's point of view, and the other half Riku's.
After Sora is visited by the same creepy hooded guy at the beginning of the last game, the party comes across a strange castle called Castle Oblivion. Sensing that Riku and King Mickey are inside, they enter and instantly realize they've forgotten all their attacks and magic (surprise!) and that Jiminy Cricket's journal has been erased. Another hooded man appears and tells them a bunch of cryptic stuff including "to lose is to find, and to find is to lose" and "to forget is to remember, and to remember is to forget". He also explains that everything in Castle Oblivion, from battles to what rooms you enter, is controlled by strange cards, including the help of Donald and Goofy during battle (see Castle Oblivion for complete rules concerning the castle's cards). After giving Sora a "world card", he disappears and the party decides to climb to the top of the castle to look for Riku and the King.
As they climb the castle, they realize that they are beginning to forget things about their journey that took place in the first Kingdom Hearts game. In short, this is because the castle uses up memories in order to create cards, which are then used to change the look of the castle's rooms to match the memories. However, Sora also shockingly begins to forget about Kairi and starts to remember a second girl who loved to draw, supposedly lived on Destiny Islands and was Sora's close friend. To the player, this is alarming, as anyone who has played the first game knows there was no such girl. Additionally, the party also starts to forget about their search for Riku and Mickey.
As they head to the top floor they also come across strange hooded people, who appear to be others inside Castle Oblivion, and not illusions made from Sora's memories. They are members of Organization XIII, headed by Marluxia, who seems to be plotting an overthrow of this organization. They have lured Sora into the castle in an effort to somehow use him to their advantage.
As Sora nears the top of the castle, he remembers the second girl's name: Naminé. Through cutscenes seen only by the player, Naminé seems to be a girl being held captive by the Organization XIII members residing in the castle. She has the ability to rearrange the "links" in a person's "chain of memories", thus manipulating their memories and making them whatever she wants. Against her will, she has done this to Sora and replaced his memories of Kairi with false ones featuring herself, including a memory where Sora promises to protect her. It is through this memory that the Organization hopes to use Sora in whatever it is their plans are.
While all this stuff is going on there's a suspicious Riku running around, claiming to be the one who promised Naminé he'd protect her. As it turns out this Riku is actually a fake puppet created by Vexen, one of the Organization XIII members present in the castle. Besides fighting Sora a few times and protecting Naminé from being killed, he eventually is revealed as a fake and killed by the real Riku during his portion of the storyline... thus in the end not really mattering much.
Finally, Sora reaches the 13th and top floor of the castle and meets Naminé—to him it's a reunion, but Naminé explains what's going on and that it's actually their first time ever seeing each other. Sora tries to understand what's happening, but is still unable to push the fake promise out of his heart, using it to try and help Naminé. After killing Marluxia, and (temporarily) freeing Naminé, she offers to put Sora, Donald and Goofy into these big egg things to restore their memories to their previous state. Knowing this will erase the new positive memories of Naminé, Sora agrees to it for the sake of finding and remembering the girl who was truly "most important" to him. Before entering the egg machines, Jiminy writes one sentence into his journal: "Thank Naminé" (a quite cryptic sentence to anyone playing KH2 if they haven't played CoM).