We express the coefficients of the Hirzebruch L-polynomials in terms of certain alternating multiple zeta values. In particular, we show that every monomial in the Pontryagin classes appears with a non-zero coefficient, with the expected sign. Similar results hold for the polynomials associated to the Â-genus.