Electromagnetic wave propagation along waveguides having two-dimensionally (2-D) periodic walls with finite thickness is formulated here as an exact boundary-value problem. The dispersion relation of such a class of waveguide is systematically analyzed in terms of both phase and attenuation constants. In addition, the contour map of field components and Poynting vector are also demonstrated in this paper to verify the guiding characteristics of such a class of waveguides. In particular, the strong couplings between an incident plane wave and waveguide modes phase-matching condition are carefully examined and are employed to identify the existence of waveguide modes.