The known galaxies most dominated by dark matter (Draco, Ursa Minor and Andromeda IX) are satellites of the Milky Way and the Andromeda galaxies1-4. They are members of a class of faint galaxies, devoid of gas, known as dwarf spheroidals3-5, and have by far the highest ratio of dark to luminous matter3,6. None of the models proposed to unravel their origin7-10can simultaneously explain their exceptional dark matter content and their proximity to a much larger galaxy. Here we report simulations showing that the progenitors of these galaxies were probably gas-dominated dwarf galaxies that became satellites of a larger galaxy earlier than the other dwarf spheroidals. We find that a combination of tidal shocks and ram pressure swept away the entire gas content of such progenitors about ten billion years ago because heating by the cosmic ultraviolet background kept the gas loosely bound: a tiny stellar component embedded in a relatively massive dark halo survived until today. All luminous galaxies should be surrounded by a few extremely dark-matter-dominated dwarf spheroidal satellites, and these should have the shortest orbital periods among dwarf spheroidals because they were accreted early.