We used our database of VLT-UVES quasar spectra to build up a sample of 70 Damped Lyman-\alpha (DLA) or strong sub-DLA systems with total neutral hydrogen column densities of \log N(H I) \ga 20 and redshifts in the range 1.7<z_{\rm abs}<4.3. For each of the systems, we measured the metallicities relative to solar in an homogeneous manner, X/H (with {\rm X}={\rm Zn}, or S or Si), and the velocity widths of low-ionization line profiles, \Delta V. For the first time, we provide evidence for a correlation between DLA metallicity and line profile velocity width, which is detected at the 6.1\sigma significance level. This confirms the trend previously observed in a much smaller sample by Wolfe & Prochaska (1998). The best-fit linear relation is {\rm X}/{\rm H}=1.55(\pm 0.12) \log\Delta V-4.33(\pm 0.23), with \Delta V expressed in km s super(-1). The slope of the DLA velocity- metallicity relation is the same within uncertainties between the higher ( 2.43$--> z_{\rm abs}>2.43) and the lower ( z_{\rm abs}\le 2.43) redshift halves of our sample. However, the two populations of systems are statistically different. There is a strong redshift evolution in the sense that the median metallicity and median velocity width increase with decreasing redshift. We argue that the existence of a DLA velocity- metallicity correlation, over more than a factor of 100 spread in metallicity, is probably the consequence of an underlying mass-metallicity relation for the galaxies responsible for DLA absorption lines. Assuming a simple linear scaling of the galaxy luminosity with the mass of the dark- matter halo, we find that the slope of the DLA velocity-metallicity relation is consistent with that of the luminosity-metallicity relation derived for local galaxies. If the galaxy dynamical mass is indeed the dominant factor setting up the observed DLA velocity-metallicity correlation, then the DLA systems exhibiting the lowest metallicities among the DLA population should, on average, be associated with galaxies of lower masses (e.g., gas-rich dwarf galaxies). In turn, these galaxies should have the lowest luminosities among the DLA galaxy population. This could explain the difficulties of detecting high-redshift DLA galaxies in emission.