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].