We theoretically and experimentally demonstrate the existence of complete surface acoustic wave band gaps in surface phonon-polariton phononic crystals, in a completely monolithic structure formed from a two-dimensional honeycomb array of hexagonal shape domain-inverted inclusions in single crystal piezoelectric Z-cut lithium niobate. The band gaps appear at a frequency of about twice the Bragg band gap at the center of the Brillouin zone, formed through phonon-polariton coupling. The structure is mechanically, electromagnetically, and topographically homogeneous, without any physical alteration of the surface, offering an ideal platform for many acoustic wave applications for photonics, phononics, and microfluidics.