Indirect searches for the cosmological dark matter have become ever more competitive during the past years. Here, we report the first full calculation of leading electroweak corrections to the annihilation rate of supersymmetric neutralino dark matter. We find that these corrections can be huge, partially due to contributions that have been overlooked so far. Our results imply a significantly enhanced discovery potential of this well motivated dark matter candidate with current and upcoming cosmic ray experiments, in particular for gamma rays and models with somewhat small annihilation rates at the tree level.