Black-hole spectroscopy is arguably the most promising tool to test gravity in extreme regimes and to probe the ultimate nature of black holes with unparalleled precision. These tests are currently limited by the lack of a ringdown parametrization that is both robust and accurate. We develop an observable-based parametrization of the ringdown of spinning black holes beyond general relativity, which we dub ParSpec (Parametrized Ringdown Spin Expansion Coefficients). This approach is perturbative in the spin, but it can be made arbitrarily precise (at least in principle) through a high-order expansion. It requires O(10) ringdown detections, which should be routinely available with the planned space mission LISA and with third-generation ground-based detectors. We provide a preliminary analysis of the projected bounds on parametrized ringdown parameters with LISA and with the Einstein Telescope, and discuss extensions of our model that can be straightforwardly included in the future.