Large dark matter overdensities can form around black holes of astrophysical and primordial origin as they form and grow. This "dark dress" inevitably affects the dynamical evolution of binary systems, and induces a dephasing in the gravitational waveform that can be probed with future interferometers. In this paper, we introduce a new analytical model to rapidly compute gravitational waveforms in presence of an evolving dark matter distribution. We then present a Bayesian analysis determining when dressed black hole binaries can be distinguished from GR-in-vacuum ones and how well their parameters can be measured, along with how close they must be to be detectable by the planned Laser Interferometer Space Antenna (LISA). We show that LISA can definitively distinguish dark dresses from standard binaries and characterize the dark matter environments around astrophysical and primordial black holes for a wide range of model parameters. Our approach can be generalized to assess the prospects for detecting, classifying, and characterizing other environmental effects in gravitational wave physics.