We report the first observation of an anisotropy in the arrival direction of cosmic rays with energies in the multi-TeV region in the Southern 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 over 22 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 are suitable 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 degrees and a median energy of similar to 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.) x 10(-4).