Epitaxial self-assembled ferro(i)magnetic spinel (CoFe2O4 (CFO)) and ferroelectric bismuth layered perovskite (Bi5Ti3FeO15 (BTFO)) pillar-matrix nanostructures are demonstrated on (001) single-crystalline strontium titanate substrates. The CFO remains embedded in the BTFO matrix as vertical pillars (∼50 nm in diameter) up to a volume fraction of 50%. Piezoresponse force microscopy experiments evidence a weak out-of-plane and a strong in-plane ferroelectricity in the BTFO phase, despite previously reported paraelectricity along the c-axis in a pure BTFO film. Phenomenological Landau-Ginzburg-Devonshire-based thermodynamic computations show that the radial stress induced by the CFO nanopillars can influence these ferroelectric phases, thus signifying the importance of the nanopillars. The CFO pillars demonstrate robust ferromagnetic hysteresis loops with little degradation in the saturation magnetization (ca. 4 μB/f.u.). Thus BTFO-CFO nanocomposites show significant promise as a lead-free magnetoelectric materials system.