Quantum metrology aims to use entanglement and other quantum resources to improve precision measurement(1). An interferometer using N independent particles to measure a parameter X can achieve at best the standard quantum limit of sensitivity, delta X proportional to N-1/2. However, using N entangled particles and exotic states(2), such an interferometer(3) can in principle achieve the Heisenberg limit, delta X proportional to N-1. Recent theoretical work(4-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 delta X proportional to N-k with appropriate entangled states and delta X proportional to N-(k-1/2) even without entanglement(7). Here we demonstrate 'super-Heisenberg' scaling of delta X proportional to N-3/2 in a nonlinear, non-destructive(8,9) measurement of the magnetization(10,11) of an atomic ensemble(12). We use fast optical nonlinearities to generate a pairwise photon-photon interaction(13) (corresponding to k = 2) while preserving quantum-noise-limited performance(7,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 theory(13). 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.