Between 2009 May and 2010 May, the IceCube neutrino detector at the South Pole recorded 32 billion muons generated in air showers produced by cosmic rays with a median energy of 20TeV. With a data set of this size, it is possible to probe the southern sky for per-mil anisotropy on all angular scales in the arrival direction distribution of cosmic rays. Applying a power spectrum analysis to the relative intensity map of the cosmic ray flux in the southern hemisphere, we show that the arrival direction distribution is not isotropic, but shows significant structure on several angular scales. In addition to previously reported large-scale structure in the form of a strong dipole and quadrupole, the data show small-scale structure on scales between 15° and 30°. The skymap exhibits several localized regions of significant excess and deficit in cosmic ray intensity. The relative intensity of the smaller-scale structures is about a factor of five weaker than that of the dipole and quadrupole structure. The most significant structure, an excess localized at (right ascension α = 1224 and declination δ = -474), extends over at least 20° in right ascension and has a post-trials significance of 5.3σ. The origin of this anisotropy is still unknown. © 2011. The American Astronomical Society. All rights reserved.