The IceCube Neutrino Observatory is a large Cherenkov detector instrumenting of Antarctic ice. The detector can be used to search for signatures of particle physics beyond the Standard Model. Here, we describe the search for non-relativistic, magnetic monopoles as remnants of the Grand Unified Theory (GUT) era shortly after the Big Bang. Depending on the underlying gauge group these monopoles may catalyze the decay of nucleons via the Rubakov-Callan effect with a cross section suggested to be in the range of to . In IceCube, the Cherenkov light from nucleon decays along the monopole trajectory would produce a characteristic hit pattern. This paper presents the results of an analysis of first data taken from May 2011 until May 2012 with a dedicated slow-particle trigger for DeepCore, a subdetector of IceCube. A second analysis provides better sensitivity for the brightest non-relativistic monopoles using data taken from May 2009 until May 2010. In both analyses no monopole signal was observed. For catalysis cross sections of the flux of non-relativistic GUT monopoles is constrained up to a level of at a 90 % confidence level, which is three orders of magnitude below the Parker bound. The limits assume a dominant decay of the proton into a positron and a neutral pion. These results improve the current best experimental limits by one to two orders of magnitude, for a wide range of assumed speeds and catalysis cross sections.