We report on the coupling between ferroelectric and magnetic order parameters in a nanostructured BaTiO3-CoFe2O4 ferroelectromagnet. This facilitates the interconversion of energies stored in electric and magnetic fields and plays an important role in many devices, including transducers, field sensors, etc. Such nanostructures were deposited on single-crystal SrTiO3 (001) substrates by pulsed laser deposition from a single Ba-Ti-Co-Fe-oxide target. The films are epitaxial in-plane as well as out-of-plane with self-assembled hexagonal arrays of CoFe2O4 nanopillars embedded in a BaTiO3 matrix. The CoFe2O4 nanopillars have uniform size and average spacing of 20 to 30 nanometers. Temperature-dependent magnetic measurements illustrate the coupling between the two order parameters, which is manifested as a change in magnetization at the ferroelectric Curie temperature. Thermodynamic analyses show that the magnetoelectric coupling in such a nanostructure can be understood on the basis of the strong elastic interactions between the two phases.