In some previous papers we have defined and studied a 'magnetic' pseudodifferential calculus as a gauge covariant generalization of the Weyl calculus when a magnetic field is present. In this paper we extend the standard Fourier Integral Operators Theory to the case with a magnetic field, proving composition theorems, continuity theorems in 'magnetic' Sobolev spaces and Egorov type theorems. The main application is the representation of the evolution group generated by a 1-st order 'magnetic' pseudodifferential operator (in particular the relativistic Schr��dinger operator with magnetic field) as such a 'magnetic' Fourier Integral Operator. As a consequence of this representation we obtain some estimations for the distribution kernel of this evolution group and a result on the propagation of singularities.