We derive upper limits on the strength of elastic, velocity-dependent dark-matter–proton interactions from the observed population of Milky Way satellite galaxies. In particular, we study the effects of dark matter interactions in the early Universe on the small-scale linear matter power spectrum, assuming the momentum-transfer cross section is a power law of the relative particle velocity v with a free normalizing amplitude, i.e., σMT = σ0 vn. If the power spectrum is suppressed relative to standard cosmology due to momentum and heat transfer between the dark matter and photon-baryon fluids prior to recombination, the population of satellites as tracers of structure on small scales, will be reduced accordingly. We relate the current upper limit on the minimum mass of dark matter halos (inferred from the satellite population) of (5±4)×108 M* at 95% confidence to the lower limits on the co-moving wavenumber at which the matter power spectrum is allowed to be significantly suppressed in comparison to standard (non-interacting) cosmology. We then relate the limit on the power cutoff to the limit on the strength of the interaction at hand. For a particle mass of 1 MeV, we derive upper limits of (1±4)×1027, (9±8)×1022, (1±5)×1015, and (1±6)×109 cm2, for n = 0, 2, 4, and 6, respectively. These limits represent the most stringent astrophysical bounds on these interaction models to date, and they improve relative to limits derived from the cosmic microwave background by roughly 2, 3, and 4 orders of magnitude, for n = 0, 2, and 4, respectively.