A family of vertex algebras whose universal Verma modules coincide with the cohomology of affine Laumon spaces is found. This result is based on an explicit expression for the generating function of Poincare polynomials of these spaces. There is a variant of quantum Hamiltonian reduction that realizes vertex algebras which we call iterated W-algebras and our main conjecture is that the vertex algebras associated to the affine Laumon spaces are subalgebras of iterated W-algebras.