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 2009 May and 2010 May. The data include a total of 33 × 109 muon events with a median angular resolution of ∼3°. 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 sky map shows a different anisotropy structure including a deficit with a post-trial significance of .6.3σ. 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.