We report the first observation of an anisotropy in the arrival direction of cosmic rays with energies in the multi-TeV region in theSouthern sky using data from the IceCube detector. Between 2007 June and 2008 March, the partially deployed IceCube detector was operated in a configuration with 1320 digital optical sensors distributed over22 strings at depths between 1450 and 2450 m inside the Antarctic ice. IceCube is a neutrino detector, but the data are dominated by a large background of cosmic-ray muons. Therefore, the background data aresuitable for high-statistics studies of cosmic rays in the southern sky. The data include 4.3 billion muons produced by downward-going cosmic-ray interactions in the atmosphere; these events were reconstructed with a median angular resolution of 3° and a median energy of ∼20 TeV. Their arrival direction distribution exhibits an anisotropy in right ascension with a first-harmonic amplitude of (6.4±0.2 stat.±0.8 syst.) × 10-4. © 2010 The American Astronomical Society.