In this paper, we present an exact formulation for the three-dimensional boundary-value problem of waveguiding by a two-dimensional periodic impedance surface in a uniform medium. The dispersion characteristics of such a structure are rigorously analyzed in terms of the complete set of both TE- and TM-polarized plane waves in the uniform medium. The results are systematically expressed in the form of the Brillouin diagram; thereby, in comparison to the one-dimensional case, a host of new and interesting phenomena are identified and physically explained.