Ultra high-density magnetic data storage of 1Tb per square inch or larger requires magnetic grains typically <5 nm diameters. To avoid entering super-paramagnetic phase, thermal stability of such small magnetic nano-grain demands materials with very large magneto-crystalline anisotropy, which makes the data write process almost impossible, even when Heat Assisted Magnetic Recording (HAMR) technology is deployed. Here we propose an alternative method of strengthening the thermal stability of the magnetic nano-grains via magneto-electric coupling between the magnetic data storage layer and a piezo-ferroelectric substrate. Using Stoner-Wohlfarth single domain model applied to a magnetic nano-grain we show that the correct tuning of the multiferroic coupling can increase the effective magneto-crystalline anisotropy of the magnetic grains making them stable beyond the super-paramagnetic limit. However, the effective magnetic anisotropy can also be lowered or even switched off during the write process by simply altering the applied voltage to the substrate. Based on these effects, we propose two magnetic data storage protocols, one of which could potentially replace HAMR technology, with both schemes promising unprecedented increases in the data storage areal density beyond the super-paramagnetic size limit.