We study experimentally the fundamental limits of sensitivity of an atomic radio-frequency magnetometer. First we apply an optimal sequence of state preparation, evolution, and the back-action evading measurement to achieve a nearly projection noise limited sensitivity. We furthermore experimentally demonstrate that Einstein-Podolsky-Rosen (EPR) entanglement of atoms generated by a measurement enhances the sensitivity to pulsed magnetic fields. We demonstrate this quantum limited sensing in a magnetometer utilizing a truly macroscopic ensemble of 1.5*10^12 atoms which allows us to achieve sub-femtoTesla/sqrt(Hz) sensitivity.