The Milky Way is expected to be embedded in a halo of dark matter particles, with the highest density in the central region, and decreasing density with the halo-centric radius. Dark matter might be indirectly detectable at Earth through a flux of stable particles generated in dark matter annihilations and peaked in the direction of the Galactic Center. We present a search for an excess flux of muon (anti-) neutrinos from dark matter annihilation in the Galactic Center using the cubic-kilometer-sized IceCube neutrino detector at the South Pole. There, the Galactic Center is always seen above the horizon. Thus, new and dedicated veto techniques against atmospheric muons are required to make the southern hemisphere accessible for IceCube. We used 319.7 live-days of data from IceCube operating in its 79-string configuration during 2010 and 2011. No neutrino excess was found and the final result is compatible with the background. We present upper limits on the self-annihilation cross-section, < sAv >, for WIMP masses ranging from 30GeV up to 10TeV, assuming cuspy (NFW) and flat-cored (Burkert) dark matter halo profiles, reaching down to similar or equal to 4 . 10(-24) cm(3) s(-1), and similar or equal to 2.6 . 10(-23) cm(3) s(-1) for the nu(nu) over bar channel, respectively.