Nanocomposite films consisting of BaTiO3 and CeO2 have been grown by a self-assembled approach. The composite structure of those films varied with the volume fractions of BaTiO3 and CeO2. A BaTiO3 in the form of inclined nano-fibers embedded in CeO2 matrix was obtained for CeO2-rich composition, which results in an appreciable tunability with a very low permittivity of 50. The observed tunable properties imply the competitive potential of BaTiO3-CeO2 composite as an alternative tunable material.