An efficient and accurate spectral method is presented for scattering problems with rough surfaces. A probabilistic framework is adopted by modeling the surface roughness as random process. An improved boundary perturbation technique is employed to transform the original Helmholtz equation in a random domain into a stochastic Helmholtz equation in a fixed domain. The generalized polynomial chaos (gPC) is then used to discretize the random space; and a Fourier-Legendre method to discretize the physical space. These result in a highly efficient and accurate spectral algorithm for acoustic scattering from rough surfaces. Numerical examples are presented to illustrate the accuracy and efficiency of the present algorithm.