The electrical properties of nanostructured, heavily yttria- or samaria-doped ceria ceramics are studied as a function of grain size using electrochemical impedance spectroscopy (EIS). A remarkable enhancement in the total ionic conductivity of about one order of magnitude is found in nanostructured samples, compared with the intrinsic bulk conductivity of conventional microcrystalline ceramics. This effect is attributed to the predominance of grain-boundary conduction in the nanostructured materials, coupled with an increase in the grain-boundary ionic diffusivity with decreasing grain size.