Rayleigh-Bloch surface waves arise in many physical contexts including water waves and acoustics. They represent disturbances travelling along an infinite periodic structure. In the absence of any existence results, a number of authors have previously computed such modes for certain specific geometries. Here we prove that such waves can exist in the absence of any incident wave forcing for a wide class of structures.