We present a search for ultra-relativistic magnetic monopoles with the Pierre Auger Observatory. Such particles, possibly a relic of phase transitions in the early universe, would deposit a large amount of energy along their path through the atmosphere, comparable to that of ultrahigh-energy cosmic rays (UHECRs). The air shower profile of a magnetic monopole can be effectively distinguished by the fluorescence detector from that of standard UHECRs. No candidate was found in the data collected between 2004 and 2012, with an expected background of less than 0.1 event from UHECRs. The corresponding 90% confidence level (C.L.) upper limits on the flux of ultra-relativistic magnetic monopoles range from $10^{-19}$ (cm$^{2}$ sr s)$^{-1}$ for a Lorentz factor $gamma=10^9$ to $2.5 times10^{-21}$ (cm$^{2}$ sr s)$^{-1}$ for $gamma=10^{12}$. These results - the first obtained with a UHECR detector - improve previously published limits by up to an order of magnitude.