A planar surface on which a scalar wave satisfies the Neumann boundary conditions does not support a surface wave. However, a structured Neumann surface can support such a wave. By means of a Rayleigh equation for a scalar field in the region above the two-dimensional rough surface of a semi-infinite medium on which the Neumann boundary condition is satisfied, we derive the dispersion relation for surface waves on both doubly periodic and randomly rough surfaces. Dispersion curves for these waves on doubly periodic surfaces with three forms of the surface profile function are presented together with dispersion curves for surface waves on a two-dimensional randomly rough surface.