An MRAM is disclosed that has a MTJ comprised of a ferromagnetic layer with a magnetization direction along a first axis, a super-paramagnetic (SP) free layer, and an insulating layer formed therebetween. The SP free layer has a remnant magnetization that is substantially zero in the absence of an external field, and in which magnetization is roughly proportional to an external field until reaching a saturation value. In one embodiment, a separate storage layer is formed above, below, or adjacent to the MTJ and has uniaxial anisotropy with a magnetization direction along its easy axis which parallels the first axis. In a second embodiment, the storage layer is formed on a non-magnetic conducting spacer layer within the MTJ and is patterned simultaneously with the MTJ. The SP free layer may be multiple layers or laminated layers of CoFeB. The storage layer may have a SyAP configuration and a laminated structure.