It has been recently demonstrated that the 125 GeV Higgs boson can mediate a long-range force between TeV-scale particles, that can impact considerably their annihilation due to the Sommerfeld effect, and hence the density of thermal relic dark matter. In the presence of long-range interactions, the formation and decay of particle-antiparticle bound states can also deplete dark matter significantly. We consider the Higgs boson as mediator in the formation of bound states, and compute the effect on the dark matter abundance. To this end, we consider a simplified model in which dark matter co-annihilates with coloured particles that have a sizeable coupling to the Higgs. The Higgs-mediated force affects the dark matter depletion via bound state formation in several ways. It enhances the capture cross-sections due to the attraction it mediates between the incoming particles, it increases the binding energy of the bound states, hence rendering their ionisation inefficient sooner in the early universe, and for large enough couplings, it can overcome the gluon repulsion of certain colour representations and give rise to additional bound states. Because it alters the momentum exchange in the bound states, the Higgs-mediated force also affects the gluon-mediated potential via the running of the strong coupling. We comment on the experimental implications and conclude that the Higgs-mediated potential must be taken into account when circumscribing the viable parameter space of related models.