We propose a multi-messenger probe of QCD axion Dark Matter based on observations of black hole-neutron star binary inspirals. It is suggested that a dense Dark Matter spike may grow around intermediate mass black holes ($10^{3}-10^{5} mathrm{,M_{odot}}$). The presence of such a spike produces two unique effects: a distinct phase shift in the gravitational wave strain during the inspiral and an enhancement of the radio emission due to the resonant axion-photon conversion occurring in the neutron star magnetosphere throughout the inspiral and merger. Remarkably, the observation of the gravitational wave signal can be used to infer the Dark Matter density and, consequently, to predict the radio emission. We study the projected reach of the LISA interferometer and next-generation radio telescopes such as the Square Kilometre Array. Given a sufficiently nearby system, such observations will potentially allow for the detection of QCD axion Dark Matter in the mass range $10^{-7},mathrm{eV}$ to $10^{-5},mathrm{eV}$.