NiO-coated YSZ powder was prepared using heterogeneous precipitation of Ni hydroxides on YSZ particle surface and high energy milling. The powders were characterized by TG/DTA, XRD, XPS, and SEM. Amorphous Ni precipitate completely decomposed into NiO at $500^{circ}C$ and the growth of NiO crystallites was constrained by the core particles. Nanocrystalline NiO-coated YSZ core-shell structure powder could be obtained after calcination at $800^{circ}C$ for 2 h. A core-shell powder compact, due to high sinterability, showed a near theoretical density at $1350^{circ}C$. After reduction at $900^{circ}C$, interpenetrating Ni-YSZ microstructure with very uniformly distributed fine Ni and YSZ grains and pores was observed. In contrast, the mechanically mixed oxide sample showed less uniform distribution of pores and larger discontinuous We particles as compared with the core-shell samples.