Super Mario 64/The Secret Aquarium
In the room where you enter Jolly Roger Bay, go to the right and backflip into the hole in the wall.
This stage is underwater. To get the star, get all 8 red coins. They are found in the bottom corners and on the sides of the stage. Be careful though: there is no air, so you will need to rely on coins to survive.