We experimentally demonstrate, for the first time, propagation loss reduction via graded-index (GRIN) cladding layers in high-index-contrast (HIC) glass waveguides. We show that scattering loss arising from sidewall roughness can be significantly reduced without compromising the high-index-contrast condition, by inserting thin GRIN cladding layers with refractive indices intermediate between the core and topmost cover of a strip waveguide. Loss as low as 1.5 dB/cm is achieved in small core (1.6 μm × 0.35 μm), high-index-contrast (Δn = 1.37) arsenic-based sulfide strip waveguides. This GRIN cladding design is generally applicable to HIC waveguide systems such as Si/SiO2.