Nanocrystalline ZrO2- and Y2O3- powders with grain sizes from 5 - 20 nm were prepared by the Inert Gas Condensation method. The powders were mixed in different fractions, pressed into,green bodies and sintered to ceramic samples with 35-49 nm average grain size. The phase, grain size and specific surface area of the powders and ceramic samples was characterized by X-ray diffraction and nitrogen adsorption. Densities from 82 to 93% of the single crystal density were determined using the Archimedes principle. The complex conductivity was measured for frequencies ranging from 20 Hz to 3 MHz at temperatures between 80 and 1100 K. The lattice relaxation, grain boundary relaxation and the contact process could be resolved and identified. The dc-conductivity for the lattice and the grain boundaries were deduced from the data. The activation energies for dc-conductivity were determined for the lattice and the grain boundaries as 0.85+/-0.05 and 1.0+/-0.1 eV, respectively.