Polymer materials are actively used in dielectric capacitors, in particular for energy storage applications. An enhancement of the stored energy density can be achieved in composites of electroactive polymers and dielectric inorganic fillers with a high dielectric permittivity. In this article, we report on the energy storage characteristics of composites of relaxor terpolymer P(VDF-TrFE-CFE) and BaZr0.2Ti0.8O3 (BZT) nanoparticles. The choice of materials was dictated by their large dielectric permittivity in the vicinity of room temperature. Free-standing composite films, with BZT contents up to 5 vol.%, were prepared by solution casting. The dielectric properties of the composites were investigated over a wide range of frequencies and temperatures. It was shown that the addition of the BZT nanoparticles does not affect the relaxor behavior of the polymer matrix, but significantly increases the dielectric permittivity. The energy storage parameters were estimated from the analysis of the unipolar polarization hysteresis loops. The addition of the BZT filler resulted in the increasing discharge energy density. The best results were achieved for composites with 1.25–2.5 vol.% of BZT. In the range of electric fields to 150 MV/m, the obtained materials demonstrate a superior energy storage density compared to other P(VDF-TFE-CFE) based composites reported in the literature.