We have conducted a search for extended energy deposition trails left by ultra-relativistic magnetic monopoles interacting in Antarctic ice. The non-observation of any satisfactory candidates in the 31 days of accumulated ANITA-II flight data results
in an upper limit on the diffuse flux of relativistic monopoles. We obtain a 90% C.L. limit of order 10^{-19}/(cm^2-s-sr) for values of Lorentz boost factor 10^{10}<gamma at the anticipated energy E=10^{16} GeV. This bound is stronger than all previously published experimental limits for this kinematic range.
