An algorithm is presented for calculating fully anharmonic vibrational state counts, state densities, and partition functions for molecules using Monte Carlo integration of classical phase space. The algorithm includes numerical evaluations of the elements of the Jacobian and is general enough to allow for sampling in arbitrary curvilinear or rectilinear coordinate systems. Invariance to the choice of coordinate system is demonstrated for vibrational state densities of methane, where we find comparable sampling efficiency when using curvilinear z-matrix and rectilinear Cartesian normal mode coordinates. In agreement with past work, we find that anharmonicity increases the vibrational state density of methane by a factor of ∼2 at its dissociation threshold. For the vinyl radical, we find a significant (∼10×) improvement in sampling efficiency when using curvilinear z-matrix coordinates relative to Cartesian normal mode coordinates. We attribute this improved efficiency, in part, to a more natural curvilinear coordinate description of the double well associated with the H2C–C–H wagging motion. The anharmonicity correction for the vinyl radical state density is ∼1.4 at its dissociation threshold. Finally, we demonstrate that with trivial parallelizations of the Monte Carlo step, tractable calculations can be made for the vinyl radical using direct ab initio potential energy surface evaluations and a composite QCISD(T)/MP2 method.