We describe a method based on precision magnetometry that can extend the search for axion-mediated spin-dependent forces by several orders of magnitude. By combining techniques used in nuclear magnetic resonance and short-distance tests of gravity, our approach can substantially improve upon current experimental limits set by astrophysics, and probe deep into the theoretically interesting regime for the Peccei-Quinn (PQ) axion. Our method is sensitive to PQ axion decay constants between 10^9 and 10^12 GeV or axion masses between 10^-6 and 10^-3 eV, independent of the cosmic axion abundance.