The game begins when Jiminy Cricket was organizing the records in his journal from his travels with Sora and his friends, his curiosity about the line "thank Naminé" results in him finding a message that he did not write: "We must return to free them from their torment" ("Their hurting will be mended when you return to end it" in Re:coded). To investigate this message, King Mickey digitizes the contents of the journal and goes into the simulated world to investigate, awakening a virtual Sora on the virtual Destiny Islands to carry out the contents of the journal to uncover the identity of "them". As Sora awakens on Destiny Islands, he encounters numerous "bugs", which take the form of red and black Heartless, covering the whole world. Upon eliminating the Heartless and destroying the bugs, Sora traverses to other worlds infected with bugs to return them to normal, following a mysterious cloaked figure upon orders from King Mickey.
Meanwhile, Heartless begin appearing within Disney Castle, and everyone finds themselves trapped in the room. To their surprise, they are saved by Data Sora as the cloaked figure reveals himself to an incarnation of Jiminy's Journal taking the form of Riku, explaining how he gave Mickey the message before digitizing him and the others into the journal before a hacking occur that traps the group. Sora sets off to give Mickey's group the means to return to their world, only to encounter Pete who also got digitized by the journal while spying on Mickey under orders from Maleficent who also arrives to make use of the data worlds. Maleficent destroys Data Sora's Keyblade and summons Heartless to attack him as Mickey and the Journal save him before Maleficent spirits the latter away. Sora makes his way through Hollow Bastion, aided by Donald and Goofy. They encounter Pete, who summons the bug-infected Journal to fight them, but Sora still manages to defeat the Journal, who falls unconscious.
Mickey arrives and informs Sora that unless the bugs are destroyed, the Journal will never awaken. Sora decides to find a way to awaken the Journal, and enters Riku's data world, losing his abilities in the process. The two visit various worlds from the Data Riku's memory and find their way back to Hollow Bastion, where they fight and defeat Maleficent. Meanwhile, King Mickey discovers that he will be returning soon to the real world, but the Journal, once completed, everything will reset and which will mean the end of Data Sora's memories. When the time comes, Sora requests more time in order to save Pete and Maleficent, who are still in the data world. Sora finds them fighting Sora's Heartless, but Pete and Maleficent are erased before he can intervene. Sora defeats Sora's Heartless, the cause of the bugs, and Mickey returns to the real world, finishing the Journal's restoration. The restored Journal appears to inform Mickey that a new world has been opened, which is the data of the data world added into the Journal. Mickey, realizing that this quest may be too dangerous for Data Sora as he has no memory of it, requests to be taken into the Data World once again.
Finding Data Sora in Traverse Town, Mickey takes him to Castle Oblivion where Data Sora is confronted by a young man wearing a black coat. He tells Sora that if he wants to know the truth, he must move forward on his own through the previous worlds he visited destroying bugs. During this time, Data Sora realizes that even if he doesn't remember someone he's met, there's still the sadness of having forgotten them which the figure attempts to warn not to let it consume him. Sora disregards this message and fights the figure, revealed to be a data incarnation of Roxas. After losing to Sora, Roxas gives him a card as Mickey appears. Sora opens the next door to find a data-based Naminé, revealing the bugs to have been an unintentional side effect of Naminé's attempt to restore Sora's memories. She then reveals Sora's nature as the "Key that connects everything" through his ties with herself, Roxas, Xion, and Axel. Furthermore, as she would soon ceased to be upon fulfilling her objective, Data Naminé tells Data Sora about three other figures (Terra, Aqua and Ven) also tied to Sora's heart who need his help. Mickey bids farewell to Data Sora and promises Data Naminé that he will inform the real Sora of this. In the final scene, he does it by sending Sora a bottled letter, containing the message found after the end-credits in Kingdom Hearts II.
In a secret ending exclusive to Re:coded, Mickey meets with Yen Sid to discuss the whereabouts of Ventus' heart, leaving only Terra to be found. However, Yen Sid also presents a shocking revelation that the destruction of "Ansem" and Xemnas is likely to bring back Master Xehanort. Fearing that this time around Xehanort may not be alone, Yen Sid orders Mickey to summon Sora and Riku to him, intending to put them through the Mark of Mastery exam to make them full-fledged Keyblade Masters in order to properly combat Master Xehanort.