We present an efficient Monte Carlo algorithm for determining the density of states which is based on the statistics of transition probabilities between states. By measuring the infinite temperature transition probabilities-that is, the probabilities associated with move proposal only-we are able to extract excellent estimates of the density of states. When this estimator is used in conjunction with a Wang-Landau sampling scheme [F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001)], we quickly achieve uniform sampling of macrostates (e.g., energies) and systematically refine the calculated density of states. This approach requires only potential energy evaluations, continues to improve the statistical quality of its results as the simulation time is extended, and is applicable to both lattice and continuum systems. We test the algorithm on the Lennard-Jones liquid and demonstrate good statistical convergence properties. (C) 2003 American Institute of Physics.