A planar perfectly conducting surface does not support a surface electromagnetic wave. However, a structured perfectly conducting surface can support such a wave. By means of a Rayleigh equation for the electric field in the vacuum above the two-dimensional rough surface of a semi-infinite perfect conductor we calculate the dispersion relation for surface electromagnetic waves on both a doubly periodic and a randomly rough surface. In the former case, if the periodic surface corrugation is sufficiently strong, the surface electromagnetic dispersion relation can have more than one branch. In the latter case, in the small roughness approximation, the binding of the surface wave to the surface is weak, but nonzero. Thus, periodically or randomly structured perfectly conducting surfaces constitute a new type of optical metamaterial. The implications of these results for the analysis of experimental results for the propagation of surface plasmon polaritons on metal surfaces in the far infrared frequency range are discussed.