We present initial results of an ESO-VLT large programme (AMAZE) aimed at determining the evolution of the mass-metallicity relation at z>3 by means of deep near-IR spectroscopy. Gas metallicities are measured, for an initial sample of nine star forming galaxies at z~3.5, by means of optical nebular lines redshifted into the near-IR. Stellar masses are accurately determined by using Spitzer-IRAC data, which sample the rest-frame near-IR stellar light in these distant galaxies. When compared with previous surveys, the mass-metallicity relation inferred at z~3.5 shows an evolution much stronger than observed at lower redshifts. The evolution is prominent even in massive galaxies, indicating that z~3 is an epoch of major action in terms of star formation and metal enrichment also for massive systems. There are also indications that the metallicity evolution of low mass galaxies is stronger relative to high mass systems, an effect which can be considered the chemical version of the galaxy downsizing. The mass-metallicity relation observed at z~3.5 is difficult to reconcile with the predictions of some hierarchical evolutionary models. Such discrepancies suggest that at z>3 galaxies are assembled mostly with relatively un-evolved sub-units, i.e. small galaxies with low star formation efficiency. The bulk of the star formation and metallicity evolution probably occurs once small galaxies are already assembled into bigger systems. Comment: 19 pages, 11 figures, A&A in press, replaced with accepted version