  One of the most promising strategies to test gravity in the strong-field,
large curvature regime is gravitational spectroscopy: the measurement of black
hole quasi-normal modes from the ringdown signal emitted in the aftermath of a
compact binary coalescence, searching for deviations from the predictions of
general relativity. This strategy is only effective if we know how quasi-normal
modes of black holes are affected by modifications of general relativity; and
if we know this for rotating black holes, since binary coalescences typically
lead to black holes with spins $J/M^2\sim 0.7$. In this article, we compute for
the first time the gravitational quasi-normal modes of rotating black holes up
to second order in the spin in a modified gravity theory. We consider
Einstein-dilaton Gauss-Bonnet gravity, one of the simplest theories which
modifies the large-curvature regime of gravity and which can be tested with
black hole observations. To enhance the domain of validity of the spin
expansion, we perform a Pad\'e resummation of the quasi-normal modes. We find
that when the second order in spin is not included, the effect of gravity
modifications may be seriously underestimated. A comparison with the general
relativistic case suggests that this approach should be accurate up to spins
$\sim 0.7$; therefore, our results can be used in the data analysis of ringdown
signals.
