The main characters are a litleo, Rex, (who is basically the equivalent of the partner) and a manaphy, Mori. Mori is basically like the player character in the main games - he looses his memory and ends up saving the world, but he is NOT a human-turned-pokemon. Slowly, over the course of the story, he starts to regain his memory. The two are part of a rescue team (which are called missioner teams, and the mon in the teams being referred to as missioners) called Team Malite. Later on another character joins their team, a pichu named Kala who is a love interest for Rex.
The story starts off in a battle between Rex and Mori. The battle is played out like a serious battle, but at the end of the battle it's revealed to be a practice battle. Then there's a flashback to when Rex found Mori passed out on the beach after a storm. Mori had woken up without even remembering his name or any of his past, and after a conversation with Rex, decides to find Jirachi so that he can wish for his memory back. Rex is surprised, because no one alive has encountered Jirachi, but Mori is really confident so he decides to go with it. Rex suggests that they form a missioner team to help them get strong enough to find Jirachi and defeat him in battle. (Because legend says that if you defeat Jirachi in battle then he will grant you a wish.) End flashback.
After a mission, Mori is attacked by a mysterious stranger. He shouts for help, which sends the attacker running, so Mori is able to get away. Afterwards, Mori and Rex speculate on it, and Rex wonders if it was someone from Mori's past who wants vengeance. The two decide to look up information on recent attacks to see if it's a coincidence that Mori attacked at their local town, Soumel's, Archivary, which is similar to a library, but also has articles, rumors, and missions that have been reported archived in it. This is when they meet Kala.
They find several reports of strange activity, including attacks on several pokemon and some pokemon going missing. They decide to investigate more at other Archivaries, which will require several days travel. Kala decides to go with them, because she has a large knowledge of the locations of Archivaries.
After several days' travel, they are attacked by a pokemon that Mori (but not his teammates) recognizes as Diancie. Strangely, Mori's water moves don't hurt it very much, despite it being a Rock/Fairy. They manage to flee using a device called the Escape Cube (the predecessor to the Escape Orb).
Waaaay later, they find out that the one behind the attacks is the soft-spoken's sister, Nenna, who, after months of research, she realizes that all the times the world has to be saved is a result of legendaries. She decides that it would be better for the world to kill all the non-important legendaries (ones that don't control a major aspect of the world, e.g. kyogre and groudon aren't important to keep the weather under control; they just mess it up, but rayquaza is, because he destroys meteors) who have, in the past, caused a world disaster.
Nenna was also behind Mori's memory loss, she blew up his underwater palace, and the resulting blast and chunks of rock knocked Mori out and he lost his memory.
Nenna actually has legends behind her cause, so defeats anyone in her path. Mori is convinced that they have to stop her, so he finds Jirachi and wishes that his team was strong enough to defeat her and her cause. Something simlar to Mega Evolution happens - they evolve to their final forms, and then gain powers of legends and become larger and more powerful, as well as changing in appearance to match their new abilities.
A huge fight begins, and Team Malite wins, but Mori's new abilities end up creating a very severe weather problem, and Mori is too exhausted to fix it. Eventually Kyogre is convinced to dissipate the weather, as she is the only one who is able. Nenna realized that all the legendaries are important, and after the legendaries vow to be more careful and guard the world from calamity, she leaves in peace.
Epilogue: Nenna has decided to help the world by setting up a rescue office to help regulate rescue teams. Mori has returned to his underwater palace, and, even after learning that his true name is Pharoris, still opts to go by Mori. Rex and Kala have decided to travel the world together as rescuers and guardians, since the Legend Evolution that happened to them makes them ill-fitted in normal society.