© 2015, The Author(s). Dark matter which is bound in the Galactic halo might self-annihilate and produce a flux of stable final state particles, e.g. high energy neutrinos. These neutrinos can be detected with IceCube, a cubic-kilometer sized Cherenkov detector. Given IceCube’s large field of view, a characteristic anisotropy of the additional neutrino flux is expected. In this paper we describe a multipole method to search for such a large-scale anisotropy in IceCube data. This method uses the expansion coefficients of a multipole expansion of neutrino arrival directions and incorporates signal-specific weights for each expansion coefficient. We apply the technique to a high-purity muon neutrino sample from the Northern Hemisphere. The final result is compatible with the null-hypothesis. As no signal was observed, we present limits on the self-annihilation cross-section averaged over the relative velocity distribution (Formula Presented.) down to ([Formula Presented.) for a dark matter particle mass of 700–1,000 GeV and direct annihilation into (Formula Presented.). The resulting exclusion limits come close to exclusion limits from γ-ray experiments, that focus on the outer Galactic halo, for high dark matter masses of a few TeV and hard annihilation channels.