Once you have obtained the Go-Goggles and hence have access to the Route 111 Desert, you can talk to the Fossil Maniac just east of Fallarbor Town. He'll tell you some information about finding fossils, so head over to the desert now.
The desert hides a mysterious tower that randomly appears. If it doesn't appear for you the first time, just exit the desert and cross to Route 112. Then head back to the desert again and check.

This is Mirage Tower. Make sure you have the Mach Bike with you, since there are cracked floors, and also bring someone who knows Rock Smash. Ascend the tower and at the top you'll find two fossils, the Root Fossil on the left and the Claw Fossil on the right. Take any one of them, and the tower will crumble and the other fossil will disappear into the sand. Not to worry, you can recover it. Head back to the Fossil Maniac in Fallarbor after you have beaten the Elite Four.

Enter the cave behind him and head all the way to the east. At the end of the cave you'll find the other fossil that disappeared into the sand before. Take the fossils to Devon Co. in Rustboro City and they'll revive them into Anorith from the Claw and Lileep from the Root Fossil. |