The surface instability of a dense plasma slab irradiated by a relativistic intense laser pulse is investigated using two-dimensional particle-in-cell simulation. When the laser pulse is incident with s-polarization, Rayleigh-Taylor-like instability is observed on the plasma surface. Later the instability propagates into the plasma bulk forming bubble structures, which propagate forward subsequently. The development of this instability depends upon the initial plasma density. At high densities such as over 20 times of the critical density, this instability is not observed obviously. This surface instability is not formed for the case of p-polarization, i.e., the Rayleigh-Taylor-like instability is anisotropic in three-dimensional geometry. It is expected that this instability can have significant effect on high harmonics generation and ion acceleration.