The IceCube Neutrino Observatory is a large Cherenkov detector instrumenting $1,mathrm{km}^3$ 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 GUT (Grand Unified Theory) era shortly after the Big Bang. These monopoles may catalyze the decay of nucleons via the Rubakov-Callan effect with a cross section suggested to be in the range of $10^{-27},mathrm{cm^2}$ to $10^{-21},mathrm{cm^2}$. 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 $10^{-22},(10^{-24}),mathrm{cm^2}$ the flux of non-relativistic GUT monopoles is constrained up to a level of $Phi_{90} le 10^{-18},(10^{-17}),mathrm{cm^{-2}s^{-1}sr^{-1}}$ 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.