We use non-perturbative lattice calculations to investigate the finite-temperature confinement transition of stealth dark matter, focusing on the regime in which this early-universe transition is first order and would generate a stochastic background of gravitational waves. Stealth dark matter extends the standard model with a new strongly coupled SU(4) gauge sector with four massive fermions in the fundamental representation, producing a stable spin-0 ‘dark baryon’ as a viable composite dark matter candidate. Future searches for stochastic gravitational waves will provide a new way to discover or constrain stealth dark matter, in addition to previously investigated direct-detection and collider experiments. As a first step to enabling this phenomenology, we determine how heavy the dark fermions need to be in order to produce a first-order stealth dark matter confinement transition.