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.