Haze, generated by floaters (semitransparent clouds, fog, snow, etc.) in the atmosphere, can significantly degrade the utilization of remote sensing images (RSIs). However, the existing techniques for single image dehazing rarely consider that the haze is superimposed by floaters and shadow, and they often aggravate the degree of the haze shadow and dark region. In this paper, a single RSI dehazing method based on robust light-dark prior (RLDP) is proposed, which utilizes the proposed hybrid model and is robust to outlier pixels. In the proposed RLDP method, the haze is first removed by a robust dark channel prior (RDCP). Then, the shadow is removed with a robust light channel prior (RLCP). Further, a cube root mean enhancement (CRME)-based stable state search criterion is proposed for solving the difficult problem of patch size setting. The experiment results on benchmark and Landsat 8 RSIs demonstrate that the RLDP method could effectively remove haze.