Some oxygen defective fluorites are non-Newnham electrostrictors, i.e., the electromechanical response does not depend on their dielectric properties. Here, we show gigantic electrostriction in nanocrystalline 25 mol% praseodymium doped ceria (PCO) bulk ceramics. The material was fabricated with a field-assisted spark plasma sintering (SPS) process from high-purity nanoscale PCO powders (<20 nm). The SPS process consolidates the powders into a single-phase, highly dense material with a homogeneous microstructure and large grain boundary extension. Various thermally and chemically stable ionic defects are incorporated into the nanostructure, leading to superior electrical conductivity. The material shows an electrostriction strain coefficient (M33) of ∼10-16 m2 V-2 at frequencies below 100 Hz at room temperature. Such performance is comparable and even superior to Newnham's electrostrictors, such as ferroelectric ceramics and polymeric actuators. Comparative analysis with polycrystals suggests that nanostructured PCO possesses electromechanically active nanodomains of Pr3+-VO pairs. Such results are unexpected and open novel insights on non-Newnham electrostrictors.