Nanocrystalline gadolinia-doped ceria (GDC) specimens with grain sizes ranging from 10 to 100 nm were studied by AC-impedance spectroscopy over the temperature range of ∼150°–∼300°C, and were analyzed by the nanograin composite model (n-GCM), which is capable of extracting local properties (grain-core conductivity, grain-boundary conductivity, grain-boundary dielectric constant) and also grain-boundary width. The grain-core dielectric constant, a necessary input parameter for the n-GCM procedure, was measured separately on a microcrystalline GDC specimen sintered from identical powders. In spite of modest increases in grain-boundary conductivity at the nanoscale, the total conductivity exhibited a monotonic decrease with decreasing grain size. This behavior was attributed to the large increase in the number of grain-boundary barriers at the nanoscale, which overwhelms the slight increase in grain-boundary conductivity. An unusual “up-and-down” behavior was observed in grain-boundary conductivity versus grain size, which was accounted for by a similar trend in the preexponential factor versus grain size. Effective grain-boundary widths, also determined by the n-GCM, exhibited a similar “up-and-down” behavior, which probably reflects the differences in thermal history from specimen-to-specimen.