Temperature dependences of the dielectric permittivity ε of (1−x)PbFe0.5Nb0.5O3-x BaFe0.5Nb0.5O3 solid solution ceramics at 100 Hz–1 MHz have been studied in the 12–500 K temperature range. To lower the conductivity values and exclude the corresponding relaxations, 1 wt% of Li2CO3 was added to the starting mixture of oxides. It was found that Li-doping is effective in lowering the conductivity only for compositions with x ≤ 0.5. The permittivity–temperature dependences of the (1−x)PbFe0.5Nb0.5O3–xBaFe0.5Nb0.5O3 compositions were found to change, as x grows, from relatively sharp frequency-independent maxima typical of usual ferroelectrics to the diffused and frequency-dependent maxima typical of relaxors and then to the saturated at low temperatures and frequency-independent ε(T) curves typical of incipient ferroelectrics and at last, to the step-like frequency-dependent ε(T) curves known for the dielectrics with Maxwell–Wagner-type polarization. The ε value of BaFe0.5Nb0.5O3 at 20 K measured at 1 MHz does not exceed 30. The character of the evolution of dielectric properties in the (1−x)PbFe0.5Nb0.5O3–x BaFe0.5Nb0.5O3 system and low ε value of BaFe0.5Nb0.5O3 implies that BaFe0.5Nb0.5O3 is a paraelectric rather than ferroelectric relaxor.