We construct natural virtual fundamental classes for nested Hilbert schemes on a nonsingular projective surface $S$. This allows us to define new invariants of $S$ that recover some of the known important cases such as Poincare invariants of Durr-Kabanov-Okonek and the stable pair invariants of Kool-Thomas. In the case of the nested Hilbert scheme of points, we can express these invariants in terms of integrals over the products of Hilbert scheme of points on $S$, and relate them to the vertex operator formulas found by Carlsson-Okounkov. The virtual fundamental classes of the nested Hilbert schemes play a crucial role in the Donaldson-Thomas theory of local-surface-threefolds that we study in [GSY17b].