We report observation of a radial dependence in the magnetic anisotropy of epitaxially strained CoFe2O4 nanopillars in a BaTiO3 matrix. This archetypal example of a multiferroic heterostructure with a self-assembling three-dimensional architecture possesses significant out-of-plane uniaxial magnetic anisotropy. The anisotropy originates from the large magnetostriction of CoFe2O4 and the state of stress within the nanocomposite. Magnetometry suggests the existence of two magnetic phases with different anisotropies. Micromagnetic simulations of a core-shell magnetic anisotropy qualitatively reproduce features of the magnetic hysteresis and elucidate the magnetization reversal mechanism: The magnetization initially reorients within the pillar core, followed by that of the shell. This is consistent with polarized small-angle neutron scattering which can be described by a CoFe2O4 magnetization that is nonuniform on nanometer length scales. As the length scale of inhomogeneity of the magnetic anisotropy is similar to estimates of the relaxation of the displacement field from the CoFe2O4−BaTiO3 interface, stress and its influence on structure provide an important route to new functionality of vertically aligned nanopillars for applications in low-power memory, computing, and sensing.