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 x 10(9) muon events with a median angular resolution of similar to 3 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 sky map 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.