Probing the QCD axion dark matter (DM) hypothesis is extremely challenging as the axion interacts very weakly with Standard Model particles. We propose a new avenue to test the QCD axion DM via transient radio signatures coming from encounters between neutron stars (NSs) and axion minihalos around primordial black holes (PBHs). We consider a general QCD axion scenario in which the PQ symmetry breaking occurs before (or during) inflation coexisting with a small fraction of DM in the form of PBHs. The PBHs will unavoidably acquire around them axion minihalos with the typical length scale of parsecs. The axion density in the minihalos may be much higher than the local DM density, and the presence of these compact objects in the Milky Way today provides a novel chance for testing the axion DM hypothesis. We study the evolution of the minihalo mass distribution in the Galaxy accounting for tidal forces and estimate the encounter rate between NSs and the dressed PBHs. We find that the encounters give rise to transient line-like emission of radio frequency photons produced by the resonant axion-photon conversion in the NS magnetosphere and the characteristic signal could be detectable with the sensitivity of current and prospective radio telescopes. It would be important to investigate in detail search strategies for such signals which would provide a novel pathway for QCD axion detection.