Quantum metrology aims to use entanglement and other quantum resources to improve precision measurement. 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 states, such an interferometer can in principle achieve the Heisenberg limit, δχ ∝ N(-1). Recent theoretical work 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 entanglement. Here we demonstrate 'super-Heisenberg' scaling of δχ ∝ N(-3/2) in a nonlinear, non-destructive measurement of the magnetization of an atomic ensemble. We use fast optical nonlinearities to generate a pairwise photon-photon interaction (corresponding to k = 2) while preserving quantum-noise-limited performance. 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 theory. 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.