Within his dream, an unconscious Klonoa is asked for help by a mysterious figure. Soon after, he falls into water and an airship piloted by sky pirate Leorina and her sidekick Tat appears, intending to take his ring. However, a priestess-in-training, Lolo, and her best friend, Popka, appear as well and save Klonoa before Leorina is able to do so, not wanting to risk losing the ring. When Klonoa comes to, he introduces himself to Lolo and Popka, and Lolo mentions that Klonoa is "the name of the Dream Traveler". Before a confused Klonoa could ask Lolo anything, they are interrupted by a Digon attack which they avoid. With Lolo powering Klonoa's ring, the group makes their way through the Sea of Tears before ringing the Spirit Bell. Believing to have rung the bell, Lolo thinks of herself as becoming a full-fledged priestess now. They then proceed to meet with the prophet Baguji, and Klonoa learns he is now in Lunatea.
While speaking to Baguji, Klonoa learns that there are bells across four kingdoms, with a fifth one that can cause chaos should it appear. The group then meets with the High Priestess, who grants Lolo the title of priestess. Klonoa is then given a new mission: he must get all the elements from each of the bells in order to prevent the fifth kingdom from appearing. During the journey, Leorina impedes Klonoa's progress by trying to steal the Wind Ring, but eventually manages to create a fake ring using gathered data to take one of the elements for herself.
Once the group reaches the Maze of Memories in Mira-Mira, Klonoa finds out about Lolo's past, that she was bullied and mocked by her peers, and after hearing about Klonoa's eventual arrival to Lunatea, wanted to accompany Klonoa to prove that she wasn't a failure. Realizing the selfish motivations in helping Klonoa, Lolo, distraught, breaks down and apologizes to Klonoa for everything, and Klonoa feels remorse. Upon reaching the Bell of Indecision, Klonoa is told that he must do battle against Polonte the Hatchling to prove he is worthy of ringing the bell. During the battle, Lolo has a confidence problem and is on the verge of giving up, saying she isn't qualified to save the world, unable to power up the Wind Ring. However, after a pep talk from Popka, Lolo regains her confidence and helps Klonoa defeat Polonte before ringing the bell.
Once the indecision element is in their hands, Klonoa and the group make their way back to Baguji's island, only to find Leorina, who had disguised herself as Baguji and steal the remaining elements. The group then makes their way back to the High Priestess, who tells them that in the past, Leorina was once a priestess of their own and went by the name "Leo". As time passed, she grew impatient and left the temple, intending to seek power on her own. Now in the present, Leorina, at the Sea of Tears, uses the elements' power to re-emerge the fifth bell and ring it, opening up the Kingdom of Sorrow, Hyuponia.
Klonoa eventually catches up with Leorina, who explains that with the power she has, she'll make everyone remember sorrow. However, she ends up being cursed by sorrow, and soon mutates into a bird-like monster, which Klonoa is forced to do battle with. Klonoa subdues Leorina, and a distraught Leorina realizes her wrongdoings before deciding to help Klonoa. With Leorina's help, Klonoa and his friends arrive in Hyuponia, where they have a final confrontation with its ruler, the King of Sorrow. He reveals that the fifth kingdom was always there, and that Lunatea put a "veil" over it, refusing to see it, and used the ark to "lift Lunatea's Veil", so he could reconnect the kingdom with Lunatea and that the world could remember sorrow. He also reveals that he had used Baguji so as to lead the heroes through false prophecies and revealing that he was the one who summoned Klonoa to Lunatea, being the voice in Klonoa's dream calling for help. The king then decides to use Klonoa as a vessel for the pain he suffered in isolation, but with help from Leorina lending him the elements from her fake ring to Klonoa's Wind Ring, the King of Sorrow is eventually defeated. Klonoa then rings the bell to reconnect Hyuponia with Lunatea. Klonoa then comforts the King and promises him that from now on, the world won't forget about sorrow, moments before the King dies in Klonoa's arms, and Klonoa being granted the Element of Sorrow.
In the aftermath, Leorina and Tat decide to help rebuild the Kingdom of Sorrow, while Lolo relinquishes her title of priestess, telling Klonoa that she will earn it on her own. Klonoa believes in Lolo, and turns to leave. While initially telling Klonoa she'll be okay since she's going to do her best, a distraught Lolo soon begins to break down in tears, saying that It's Okay to Cry and asking if she can do so now, and Klonoa and Lolo share one last, loving tearful hug. As Lolo cries inside Klonoa's arms, begging him not to go, Klonoa comforts her, telling her with a promise, "I may leave this world... but we'll always be... together. I believe that if you don't forget the sadness of this moment, we'll always be... together." Eventually, Lolo lets go of Klonoa, and with a final thank you, Klonoa walks off to an uncertain future.
During the credits, the inhabitants of the four kingdoms are shown roaming freely about in other kingdoms, while Leorina and Tat, true to their word, are shown rebuilding the Kingdom of Sorrow piece by piece.
