A series of novel negative temperature coefficient thermistor materials based on SrCexNbxWO4+4x (0.1 ≤ x ≤ 0.8) ceramics was synthesized by the solid-state route. X-ray diffraction, scanning electron microscopy, and X-ray photoelectron spectroscopy revealed that the SrCexNbxWO4+4x ceramics were composed of scheelite structural solid solution based on the SrWO4 phase and a CeNbO4.08 secondary phase that exhibited a fergusonite structure. The resistance-temperature analysis demonstrated that the resistivity ρ800 of the SrCexNbxWO4+4x ceramics decreased from 8.25 ± 0.08 × 106 to 2.52 ± 0.11 × 102 with the increase of x value, along with a decrease in the thermal constant B from 11,102 ± 97–4137 ± 37 K. It was observed that the SrCexNbxWO4+4x ceramics exhibited high resistivity and excellent aging characteristics as well as suitable B values at elevated temperatures, making it a promising candidate that can be used for the fabrication of high-temperature NTC thermistors with a wide operating temperature range.