Various extensions of the Standard Model motivate the existence of stable magnetic monopoles that could have been created during an early high-energy epoch of the Universe. These primordial magnetic monopoles would be gradually accelerated by cosmic magnetic fields and could reach high velocities that make them visible in Cherenkov detectors such as IceCube. Equivalently to electrically charged particles, magnetic monopoles produce direct and indirect Cherenkov light while traversing through matter at relativistic velocities. This paper describes searches for relativistic ( v≥0.76c ) and mildly relativistic ( v≥0.51c ) monopoles, each using one year of data taken in 2008/2009 and 2011/2012, respectively. No monopole candidate was detected. For a velocity above 0.51c the monopole flux is constrained down to a level of 1.55×10-18cm-2s-1sr-1 . This is an improvement of almost two orders of magnitude over previous limits.