We introduce an algorithm for sampling many-body quantum states in Fock space. The algorithm efficiently samples states with probability approximately proportional to an arbitrary function of the second-quantized Hamiltonian matrix element connecting the sampled state to the current state. We apply the new sampling algorithm to the recently developed semistochastic full configuration interaction quantum Monte Carlo (S-FCIQMC) method, a semistochastic implementation of the power method for projecting out the ground state energy in a basis of Slater determinants. Our new sampling method requires modest additional computational time and memory compared to uniform sampling but results in newly spawned weights that are approximately of the same magnitude, thereby greatly improving the efficiency of projection. A comparison in efficiency between our sampling algorithm and uniform sampling is performed on the all-electron nitrogen dimer at equilibrium in Dunning's cc-pVXZ basis sets with X ∈ D, T, Q, 5, demonstrating a large gain in efficiency that increases with basis set size. In addition, a comparison in efficiency is performed on three all-electron first-row dimers, B2, N2, and F2, in a cc-pVQZ basis, demonstrating that the gain in efficiency compared to uniform sampling also increases dramatically with the number of electrons. © 2016 American Chemical Society.