We report on the sputtering growth and characterization of nanostructures formed by a ferrimagnetic spinel (CoFe2O4) and a ferroelectric perovskite (BaTiO3) on (001) and (111) oriented SrTiO3 substrates. We present analysis of the crystal structure (crystal phases and lattice strain) and the surface morphology by X-ray diffractometry and by atomic force microscopy, respectively. Films grown on both substrates display phase segregation, being textured (either (001) or (111)) the films deposited at 700°C and polycrystalline the ones grown at the highest deposition temperature (800°C). The magnetic easy axis of films grown on SrTiO3(001) is out-of-plane. It is found that phase separation and island size are depending on the growth conditions and the role of adatom supersaturation during growth is discussed.