Core-shell structured CaCu3Ti4O12@TiO2 (CCTO@TiO2) nanofibers were prepared via a normal coaxial electrospinning technique with sol precursors. Polyimide (PI) nanocomposite films containing the core-shell structured CCTO@TiO2 nanofibers were fabricated by the solution casting method. The core-shell structure of the CCTO@TiO2 nanofibers was confirmed through transmission electron microscope. The percolation of the CCTO/TiO2 interfaces leads to much enhanced interfacial polarization of the CCTO@TiO2 nanofibers, which gives rise to substantially increased dielectric constant of the nanocomposites. Compared to the nanocomposites with CCTO nanofibers, the breakdown strength of the nanocomposites with CCTO@TiO2 nanofibers is also increased due to the charge shifting is limited to the interfacial zone of CCTO/TiO2 interfaces, instead of in the PI matrix to form a percolation path. For the nanocomposites with 5 vol% nanofibers, the dielectric constant of 5.55 was enhanced to 5.85 and the breakdown strength of 201 kV/mm was increased to 236 kV/mm by utilizing the TiO2 coated CCTO nanofibers, while the dielectric loss shows no obvious change. Meanwhile, the PI nanocomposite film filled with 1 vol% CCTO@TiO2 nanofibers exhibits a maximal energy density of 1.6 J/cm(3). The core-shell structured nanofibers open up an effective way to optimize the dielectric properties of polymer nanocomposites with high energy density.