Not yet reviewed by Pith; the record is open.

We performed a blind search for narrow absorption features at energies greater than 6.4 keV in a sample of 42 radio-quiet AGNs observed with XMM-Newton. We detect 36 narrow absorption lines on a total of 101 XMM-Newton EPIC pn observations. The number of absorption lines at rest-frame energies E>7 keV is 22. Their global probability to be generated by random fluctuations is very low, less than 3x10^-8, and their detection have been independently confirmed by a spectral analysis of the MOS data, with associated random probability <10^-7. We identify the lines as Fe XXV and Fe XXVI K-shell resonant absorption. They are systematically blue-shifted, with a velocity distribution ranging from zero up to 0.3c, with a peak and mean value at 0.1c. We detect variability of the lines on both EWs and blue-shifted velocities among different observations even on time-scales as short as a few days, possibly suggesting somewhat compact absorbers. Moreover, we find no significant correlation between the cosmological red-shifts of the sources and the lines blue-shifted velocities, ruling out any systematic contamination by local absorption. If we define Ultra-fast Outflows (UFOs) those highly ionized absorbers with outflow velocities higher than 10^4 km/s, then the majority of the lines are consistent with being associated to UFOs and the fraction of objects with detected UFOs in the whole sample is at least 35%. This fraction is similar for Type 1 and Type 2 sources. The global covering fraction of the absorbers is consequently estimated to be in the range C=0.4-0.6, thereby implying large opening angles. These lines indicate that UFOs are a rather common phenomenon observable in the central regions of these sources and they are probably the direct signature of AGN accretion disk winds/ejecta. The detailed photo-ionization modeling of these absorbers is presented in a companion paper.