Composite materials made of epoxy resin and barium titanate (BT) electrospun nanostructured fibers were prepared. BT fibers were synthesized from a sol based on barium acetate, titanium isopropoxide, and poly(vinyl pyrrolidone). The fibers were heat-treated at different temperatures and characterized by X-ray diffraction, scanning electron microscopy (SEM), and Raman spectroscopy. Mats of BT fibers heat-treated at 800 degrees C were embedded in epoxy resin into suitable molds. The composites were characterized by SEM, and dielectric measurements were performed by means of dielectric spectroscopy. The dielectric permittivity and dielectric modulus of epoxy resin/BT-fiber composites were measured for two types of samples: with the electrodes parallel and perpendicular to the BT fiber layers. Interestingly, composite samples with electrodes perpendicular to the fiber layers and a BT content as low as 2 vol % led to dielectric permittivities three times higher than that of pure epoxy resin.