We study the action of Fourier Integral Operators (FIOs) of Hörmander's type on , . We see, from the Beurling-Helson theorem, that generally FIOs of order zero fail to be bounded on these spaces when , the counterexample being given by any smooth non-linear change of variable. Here we show that FIOs of order are instead bounded. Moreover, this loss of derivatives is proved to be sharp in every dimension , even for phases which are linear in the dual variables. The proofs make use of tools from time-frequency analysis such as the theory of modulation spaces.