Like all Pokémon games, Pokemon Mystery Dungeon: Gates to Infinity
includes a myriad of Legendary Pokémon. However, unlike the past
Mystery Dungeon games, the methods to obtain these specific Pokémon
are incredibly varied from the simple encounters in and at the end of
Dungeons in the past ones.
After defeating the game, when you get your Pokémon Paradise rank up to Ultra, missions involving Legendary Pokémon start appearing. These missions typically end with the Legendary Pokémon joining your squad
Finally, on the left-hand noticeboard in the Pokémon Paradise, you
will get various special missions to various small dungeons.
Occasionally, you will get missions to go to strange dungeons. These
areas are just simple battles against various Boss Pokémon. These
Pokémon are not recruitable and are incredibly strong and difficult to
defeat. One, Ho-Oh, can even be battled as a Shiny Pokémon. These
missions can also be played through local multiplayer.
So even after you have completed your game, Legendary Pokemon will not just start appearing. You will firstly need to get your Rank up to Ultra and then Legendary Pokemon will gradually start appearing. However you should take note that this can vary and it is not insured when they will appear or not