We demonstrate that poly(vinylidene fluoride) (PVDF)-based percolative composites using two-dimensional (2D) MXene nanosheets as fillers exhibit significantly enhanced dielectric permittivity. The poly(vinylidene fluoride-trifluoro-ethylene-chlorofluoroehylene) (P[VDF-TrFE-CFE]) polymer embedded with 2D Ti3C2Tx nanosheets reaches a dielectric permittivity as high as 105 near the percolation limit of about 15.0 wt % MXene loading, which surpasses all previously reported composites made of carbon-based fillers in the same polymer. Up to 10 wt % MXene loading, the dielectric loss of the MXene/P(VDF-TrFE-CFE) composite indicates only an approximately fivefold increase (from 0.06 to 0.35), while the dielectric constant increased by 25 times over the same composition range. Furthermore, the ratio of permittivity to loss factor of the MXene-polymer composite is superior to that of all previously reported fillers in this same polymer. The dielectric constant enhancement effect is demonstrated to exist in other polymers as well when loaded with MXene. We show that the dielectric constant enhancement is largely due to the charge accumulation caused by the formation of microscopic dipoles at the surfaces between the MXene sheets and the polymer matrix under external applied electric field.