(abbreviated) We present the first results of the ESO large program, ``IMAGES'' which aims at obtaining robust measurements of the kinematics of distant galaxies using the multi-IFU mode of GIRAFFE on the VLT. 3D spectroscopy is essential to robustly measure the often distorted kinematics of distant galaxies (e.g., Flores et al. 2006). We derive the velocity fields and $\sigma$-maps of 36 galaxies at 0.4<z<0.75 from the kinematics of the [OII] emission line doublet, and generate a robust technique to identify the nature of the velocity fields based on the pixels of the highest signal-to-noise ratios (S/N). We have gathered a unique sample of 63 velocity fields of emission line galaxies (W0([OII]) > 15 A) at z=0.4-0.75, which are a representative subsample of the population of M_stellar>1.5x10^{10} M_sun emission line galaxies in this redshift range, and are largely unaffected by cosmic variance. Taking into account all galaxies -with or without emission lines- in that redshift range, we find that at least 41+/-7% of them have anomalous kinematics, i.e., they are not dynamically relaxed. This includes 26+/-7% of distant galaxies with complex kinematics, i.e., they are not simply pressure or rotationally supported. Our result implies that galaxy kinematics are among the most rapidly evolving properties, because locally, only a few percent of the galaxies in this mass range have complex kinematics.