Coupling dark matter to light new particles is an attractive way to combine thermal production with strong velocity-dependent self-interactions. Here we point out that in such models the dark matter annihilation rate is generically enhanced by the Sommerfeld effect, and we derive the resulting constraints from the cosmic microwave background and other indirect detection probes. For the frequently studied case of s-wave annihilation, these constraints exclude the entire parameter space where the self-interactions are large enough to address the small-scale problems of structure formation.