We have performed epitaxial growths of InN on Yttria stabilized zirconia (YSZ) (111) substrates which have steps and atomically flat terraces using pulsed laser deposition (PLD). The-epitaxial relationship between InN and YSZ turns out to be InN [1 (1) over bar 00] YSZ [1 (1) over bar0] and InN [000 (1) over bar]//YSZ [111], which gives a small lattice mismatch of 2.3%. We have found that the full width at half maximum (FWHM) for the InN (2) over bar 02 (4) over bar x-ray rocking curve is 980 arcseconds. Transmission electron microscopy (TEM) observations have revealed that the threading dislocation density in the InN films is less than 1 X 10(9) cm(-2) and the InN/YSZ hetero-interface is atomically abrupt. We have also found that the lattice relaxation starts from the beginning of the growth and ends at a film thickness of approximately 5 nm. After the lattice relaxation, the surface flatness is restored and the growth proceeds in the layer-by-layer mode. (C) 2004 American Vacuum Society.