The first wild Pokémon you encounter after meeting Professor Sycamore in Lumoise Station (after becoming the new Champion) will be one of three legendary bird Pokémon from the far-off Kanto region. Only one has been spotted in Kalos, and the one that appears depends on your starter Pokémon. However, the bird will flee immediately after the battle begins, and begin roaming the region. After the first encounter, the Pokédex is able to track its location. After encountering the Pokémon eleven different times, it will travel to the Sea Spirit's Den in Azure Bay, where you finally have a chance to capture it. Consider stocking up on Ultra Balls, Dusk Balls, Quick Balls, or Timer Balls for this battle.
Fly to Snowbelle City and make your way through the Winding Woods of Route 20 again. When you reach Pokémon Village, surf upriver to find that the man that had blocked the cave entrance is gone, so you can finally investigate his claims of powerful Pokémon inside. Unlike another cave of the same name, this one features only a single small chamber. The legendary Pokémon, Mewtwo, can be found in the center of this chamber, standing with its back to the entrance.
Terminus Cave is a former coal mine that was closed due to rumors of a monster living deep inside. A chill wind blows through this forbidding cave, which houses plenty of treasure for the boldest adventurers. Though the cave was accessible when you first reached Route 18, it was impossible to reach the final chamber until now.
Pass by the old mine cart and go down the northeast stairs to the basement.
Turn south and go down a small slope to reach a fork in the road. Take the eastern path first; clear the way with Rock Smash and cross the bridge to get a Star Piece. Go back and head southwest to jump two ledges. Inspect the small rock here for a hidden Dusk Ball. Follow the path uphill and check the stalagmite near the bridge for a Hyper Potion. Cross the bridge to battle Worker Narek. Take the southern path to reach another breakable rock and a Heat Rock beyond it, then return to Worker Narek and head east. Battle Hiker Aaron and cross the bridge. Go down the slope, head south, then jump the few ledges to reach an Escape Rope and Hiker Bergin. Follow the path back to Hiker Aaron, cross the bridge, and go down the slope again. This time, head north past Worker Dimitri. Use Rock Smash to find a Moon Stone in the north wall, then go down the stairs.
Go north past Battle Girl Andrea. Use Rock Smash to follow the narrow tunnel westward; check the stalagmite at the end for a hidden Iron. Go west to get a Dusk Stone, then head northeast toward Black Belt Gunnar. The path leading north takes you to an X Attack; collect the item before heading east. Climb onto the hill to fight Battle Girl Hailey, then go north to reach an Elixir, and southeast for a Full Heal. Backtrack a bit to head south from Black Belt Ricardo. At the intersection, go northwest to find TM30 (Shadow Ball) near the mine cart, and a hidden Max Potion in the corner. Head east to battle Rangers Fern & Lee, and inspect the stalagmite behind them for a Dire Hit. Continue past them to another intersection; go west to collect an Iron Plate, then climb the stairs to the east.
Head north to fight Worker Yusif. Skirt around the side of the hill and check the stalagmite for a Max Repel. Jump the ledge to collect the Reaper Cloth, then climb back up the hill and take the stairs in the northwest.
The layout of the final chamber is shaped similarly to a windmill. Each of the four tunnels leads to a rare item. The southwest tunnel leads to an Adamant Orb, the southeast tunnel, a Lustrous Orb. The northwest tunnel holds a Griseous Orb, and the northeast tunnel leads to a hidden Big Nugget. At the point where these tunnels meet, the legendary Pokémon watches you from atop a small hill.
Having tied up all the loose ends, your final mission is to complete the Pokédex. The discovery of Kalos-native Pokémon has brought the total number of species to 721, so there is still plenty to keep you busy!