There is growing evidence for the presence of blueshifted Fe K absorption lines in a number of radio-quiet AGNs and QSOs. These may be fundamental to probe flow dynamics near supermassive black holes. Here we aim at verifying and better characterising the existence of such Fe K absorption at ~8-10 keV in the luminous Seyfert 1 galaxy Mrk509, one of the most promising target for these studies. We present a comprehensive spectral analysis of the six XMM-Newton observations of the source (for a total of ~200 ks), focusing on the detailed and systematic search for absorption features in the high-energy data. We detect several absorption features at rest-frame energies ~8-8.5 keV and ~9.7 keV. The lines are consistent with being produced by H-like iron Ka and Kb shell absorptions associated with an outflow with mildly relativistic velocity of ~0.14-0.2 c. The lines are found to be variable in energy and, marginally in intensity, implying that variations in either the column density, geometry and/or ionization structure of the outflow are common in this source.