We use time-frequency methods for the study of Fourier Integral operators (FIOs). In this paper we shall show that Gabor frames provide very efficient representations for a large class of FIOs. Indeed, similarly to the case of shearlets and curvelets frames, the matrix representation of a Fourier Integral Operator with respect to a Gabor frame is well-organized. This is used as a powerful tool to study the boundedness of FIOs on modulation spaces. As special cases, we recapture boundedness results on modulation spaces for pseudo-differential operators with symbols in $M^{\infty,1}$, for some unimodular Fourier multipliers and metaplectic operators.