New three-phase composites, destined for application as dielectrics in the manufacturing of passive elements of flexible electronics, and based on polymer (PVDF) matrix filled with powdered ceramics of the hollandite-like (KFTO(H)) structure (5.0; 7.5; 15; 30 vol.%) and carbon (MWCNT) additive (0.5; 1.0; 1.5 wt.% regarding the KFTO(H) amount), were obtained and studied by XRD, FTIR and SEM methods. Chemical composition and stoichiometric formula of the ceramic material synthesized by the sol-gel method were confirmed with the XRF analysis data. The influence of the ceramic and carbon fillers on the electrical properties of the obtained composites was investigated using impedance spectroscopy. The optimal combination of permittivity and dielectric loss values at 1 kHz (77.6 and 0.104, respectively) was found for the compositions containing K1.6Fe1.6Ti6.4O16 (30 vol.%) and MWCNTs (1.0 wt.% regarding the amount of ceramic filler).