The northern clingfish, Gobiesox maeandricus, is able to adhere to slippery, fouled and irregular surfaces in the marine intertidal environment. We have found that the fish can adhere equally well to surfaces with a broad range of surface roughness, from the finest sandpaper (R(a) = 15 µm) to textures suitable for removing finish from flooring (R(a) = 269 µm). The fishes outperform man-made suction cups, which only adhere to the smoothest surfaces. The adhesive forces of clingfish correspond to pressures 0.2-0.5 atm below ambient and are 80-230 times the body weight of the fish. The tenacity appears related to hierarchically structured microvilli around the edges of the adhesive disc that are similar in size and aspect ratio to the setae found on the feet of geckoes, spiders and insects. This points to a possible biomimetic solution to the problem of reversibly adhering to irregular, submerged surfaces.