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 June 2007 and March 2008, 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 meters 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 downgoing cosmic ray interactions in the atmosphere; these events were reconstructed with a median angular resolution of 3 degrees and a median energy of $\sim20$ TeV. Their arrival direction distribution exhibits an anisotropy in right ascension with a first harmonic amplitude of $(6.4\pm0.2 $stat$. \pm 0.8 $syst$.)\times10^{-4}$.