Quantum metrology aims to use entanglement and other quantum resources to improve precision measurement1. An interferometer using N independent particles to measure a parameter can achieve at best the standard quantum limit of sensitivity, δ ∝ N−1/2. However, using N entangled particles and exotic states2, such an interferometer3 can in principle achieve the Heisenberg limit, δ ∝ N−1. Recent theoretical work4, 5, 6 has argued that interactions among particles may be a valuable resource for quantum metrology, allowing scaling beyond the Heisenberg limit. Specifically, a k-particle interaction will produce sensitivity δ ∝ N−k with appropriate entangled states and δ ∝ N−(k−1/2) even without entanglement7. Here we demonstrate ‘super-Heisenberg’ scaling of δ ∝ N−3/2 in a nonlinear, non-destructive8, 9 measurement of the magnetization10, 11 of an atomic ensemble12. We use fast optical nonlinearities to generate a pairwise photon–photon interaction13 (corresponding to k = 2) while preserving quantum-noise-limited performance7, 14. We observe super-Heisenberg scaling over two orders of magnitude in N, limited at large numbers by higher-order nonlinear effects, in good agreement with theory13. For a measurement of limited duration, super-Heisenberg scaling allows the nonlinear measurement to overtake in sensitivity a comparable linear measurement with the same number of photons. In other situations, however, higher-order nonlinearities prevent this crossover from occurring, reflecting the subtle relationship between scaling and sensitivity in nonlinear systems. Our work shows that interparticle interactions can improve sensitivity in a quantum-limited measurement, and experimentally demonstrates a new resource for quantum metrology.