The IceCube Neutrino Observatory, situated at the geographic South Pole, was completed in December 2010. A lattice of 5160 photomultiplier tubes monitors one cubic kilometer of deep Antarctic ice in order to detect neutrinos via Cherenkov photons emitted by charged by-products of their interaction in matter. We report on IceCube's response to MeV neutrinos generated by core-collapse supernova explosions of nearby massive stars. This unique telescope was designed to detect energies greater than 100 GeV. Due to subfreezing ice temperatures, the photomultipliers' dark noise rates are particularly low. Therefore IceCube can also detect large numbers of MeV neutrinos by observing a collective rise in all photomultiplier rates on top of the dark noise. In the case of a supernova at the galactic center, IceCube's sensitivity matches that of a background free megaton-scale supernova search experiment and decreases to 20 and 6 standard deviations for star explosions at the galactic edge (30 kpc) and the Large Magellanic Cloud (50 kpc), respectively.