We present a new algorithm that improves the efficiency of the Wang and Landau algorithm or Density-of-States (DOS) based Monte-Carlo simulations by employing rejected states. The algorithm is shown to have a performance superior to that of the original Wang-Landau (F. Wang and D. P. Landau, Phys. Rev. Lett., 86, 2050, 2001) method, and the more recent configurational-temperature DOS algorithm. The performance of the method is illustrated in the context of results for the Lennard-Jones fluid.