The axion is a well-motivated dark matter candidate, but is challenging to search for. We propose a new way to search for QCD axion and axion-like-particle (ALP) dark matter. Nuclei that are interacting with the background axion dark matter acquire time-varying CP-odd nuclear moments such as an electric dipole moment. In analogy with nuclear magnetic resonance, these moments cause precession of nuclear spins in a material sample in the presence of a background electric field. This precession can be detected through high-precision magnetometry. With current techniques, this experiment has sensitivity to axion masses below 10^-9 eV, corresponding to theoretically well-motivated axion decay constants around the grand unification and Planck scales. With improved magnetometry, this experiment could ultimately cover the entire range of masses below 10^-6 eV, just beyond the region accessible to current axion searches. A discovery in such an experiment would not only reveal the nature of dark matter and confirm the axion as the solution of the strong CP problem, but would also provide a glimpse of physics at the highest energy scales, far beyond what can be directly probed in the laboratory.