In this paper we report the first observation in the Southern hemisphere of an energy dependence in the Galactic cosmic ray anisotropy up to a few hundred TeV. This measurement was performed using cosmic ray induced muons recorded by the partially deployed IceCube observatory between May 2009 and May 2010. The data include a total of 33$times 10^{9}$ muon events with a median angular resolution of $sim3^{circ}$ degrees. A sky map of the relative intensity in arrival direction over the Southern celestial sky is presented for cosmic ray median energies of 20 and 400 TeV. The same large-scale anisotropy observed at median energies around 20 TeV is not present at 400 TeV. Instead, the high energy skymap shows a different anisotropy structure including a deficit with a post-trial significance of -6.3$sigma$. This anisotropy reveals a new feature of the Galactic cosmic ray distribution, which must be incorporated into theories of the origin and propagation of cosmic rays.