We used our database of ESO VLT-UVES spectra of quasars to build up a sample of 67 Damped Lyman-alpha (DLA) systems with redshifts 1.7<zabs<3.7. For each system, we measured average metallicities relative to Solar, [X/H] (with either X=Zn, S or Si), and the velocity widths of low-ionization line profiles, W1. We find that there is a tight correlation between the two quantities, detected at the 5sigma significance level. The existence of such a correlation, over more than two orders of magnitude spread in metallicity, is likely to be the consequence of an underlying mass-metallicity relation for the galaxies responsible for DLA absorption lines. The best-fit linear relation is [X/H]=1.35(pm 0.11)log W1 -3.69(pm 0.18)$ with W1 expressed in km/s. While the slope of this velocity-metallicity relation is the same within uncertainties between the higher and the lower redshift bins of our sample, there is a hint of an increase of the intercept point of the relation with decreasing redshift. This suggests that galaxy halos of a given mass tend to become more metal-rich with time. Moreover, the slope of this relation is consistent with that of the luminosity-metallicity relation for local galaxies. The DLA systems having the lowest metallicities among the DLA population would therefore, on average, correspond to the galaxies having the lowest masses. In turn, these galaxies should have the lowest luminosities among the DLA galaxy population. This may explain the recent result that the few DLA systems with detected Ly-alpha emission have higher than average metallicities.