This study reports a self-assembled multiferroic nanostructure, composed of PbTiO3 (PTO) pillars embedded in a CoFe2O4 (CFO) matrix, deposited on MgO(001) by pulsed laser deposition. The epitaxial relationship in the PTO-CFO nanostructure is (100)  P T O (001)  C F O (001)  M g O, confirming the in-plane aligned polarization of PTO. The perpendicular magnetic anisotropy of this thin film results from the magnetoelastic anisotropy that exceeds the shape anisotropy. The increased frequency and the enhanced intensity of the tetrahedral (T-) site phonon modes by increasing the magnetic field indicate strong magnetoelastic coupling through magnetostriction in this multiferroic nanostructure. The anisotropic Raman strength enhancement of the T-site phonon along different directions suggests the magnetoelastic coupling is most efficient in the in-plane direction.