Warden's Quest

Warden’s Quest is required to obtain HM06 Rock Smash.

To start the quest, speak to Warden in Fuchsia City.  He’s in the building with the red roof on the south side of the city to the right of the Pokemon Center.  He will give you a quest which requires you to find his teeth.

Travel to the Safari Zone to retrieve his Gold Teeth.  You can also grab HM03 Surf while you’re there.

Once you grab his Gold Teeth, return them to Warden and he will give you HM06 Rock Smash.

Image from PokeTwo.com