We have calculated the dispersion relation for surface polaritons propagating near the interface between a semi-infinite polycrystalline dielectric and a vacuum. A small anisotropy of single-crystal grains was assumed. The obtained complex frequency change is \ensuremath{\Delta}\ensuremath{\omega}=\ensuremath{\omega}(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$)-${\mathrm{\ensuremath{\omega}}}_{0}$(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$), where \ensuremath{\omega}(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$) is the frequency of the surface polariton on the polycrystalline substratum and ${\mathrm{\ensuremath{\omega}}}_{0}$(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$) is the frequency of the surface polariton on the reference isotropic substratum. Re\ensuremath{\Delta}\ensuremath{\omega}(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$) describes the frequency shift of the surface polariton due to the polycrystallinity, while Im\ensuremath{\Delta}\ensuremath{\omega}(${\mathrm{\ensuremath{\kappa}}}_{\mathrm{\ensuremath{\parallel}}}$) describes the attenuation of the wave caused by the spatial fluctuations of the dielectric tensor resulting from the random orientations of the grains composing the medium. This mechanism of the attenuation of surface waves has been compared with the dissipative losses and the attenuation due to the surface roughness.