Structure formation with cold dark matter (CDM) predicts halos with a central density cusp, which are observationally disfavored. If CDM particles have an annihilation cross section sigma*v ~ 10**(-29) (m/GeV) cm**2, then annihilations will soften the cusps. We discuss plausible scenarios for avoiding the early Universe annihilation catastrophe that could result from such a large cross section. The predicted scaling of core density with halo mass depends upon the velocity dependence of sigma*v, and s-wave annihilation leads to a core density nearly independent of halo mass, which seems consistent with observations.

Matches version accepted for publication in Physical Review Letters. Included the effect of adiabatic expansion. Some changes in the abstract. Conclusions unchanged