A novel metasurface based on random phase gradients is proposed for radar cross-section (RCS) reduction. In this work, wideband, polarization-independent, wide-angle RCS reduction is realized for both circularly polarized (CP) waves and linearly polarized (LP) waves, respectively. Thus, true polarization-independent RCS reduction is realized by the proposed metasurface. This proposed metasurface is composed of different types of units, and these units do not have certain periods. Under both CP incidence and LP incidence, random phase gradients can be formed on the proposed metasurface. The incidence can be diffused because of these random phase gradients, resulting in multi-polarization, polarization-independent, wide-angle RCS reduction. The 10 dB RCS reduction ranges from 12.6 GHz to 17.0 GHz and 18 GHz to 22 GHz for right-hand circularly polarized incident waves, and from 12.4 GHz to 17.0 GHz and 18.0 GHz to 21.8 GHz for left-hand circularly polarized incident waves. Meanwhile, the 10 dB RCS reduction ranges from 12.0 GHz to 17.0 GHz for x-polarized incident waves and from 13.0 GHz to 17.0 GHz and 17.6 to 21.8 GHz for y-polarized incident waves. Both the simulation and experimental results verify the value of this proposed metasurface in stealth technology.