We report on the observation of a significant deficit of cosmic rays from the direction of the Moon with the IceCube detector. The study of this "Moon shadow" is used to characterize the angular resolution and absolute pointing capabilities of the detector. The detection is based on data taken in two periods before the completion of the detector: between April 2008 and May 2009, when IceCube operated in a partial configuration with 40 detector strings deployed in the South Pole ice, and between May 2009 and May 2010 when the detector operated with 59 strings. Using two independent analysis methods, the Moon shadow has been observed to high significance (> 6 sigma) in both detector configurations. The observed location of the shadow center is within 0.2 degrees of its expected position when geomagnetic deflection effects are taken into account. This measurement validates the directional reconstruction capabilities of IceCube.