The shape dependence for the technologically important nickel oxide (NiO) nanocrystals on (001) strontium titanate substrates is investigated under the generalized Wulff-Kaichew (GWK) theorem framework. It is found that the shape of the NiO nanocrystals is primarily governed by the existence (or absence) of interfacial strain. Nanocrystals that have a fully pseudomorphic interface with the substrate (i.e. the epitaxial strain is not relaxed) form an embedded smooth ball-crown morphology with {001}, {011}, {111} and high-index {113} exposed facets with a negative Wulff point. On the other hand, when the interfacial strain is relaxed by misfit dislocations, the nanocrystals take on a truncated pyramidal shape, bounded by {111} faces and a {001} flat top, with a positive Wulff point. Our quantitative model is able to predict both experimentally observed shapes and sizes with good accuracy. Given the increasing demand for hetero-epitaxial nanocrystals in various physio-chemical and electro-chemical functional devices, these results lay the important groundwork in exploiting the GWK theorem as a general analytical approach to explain hetero-epitaxial nanocrystal growth on oxide substrates governed by interface strain.