The role of substrate orientation on interface registry and nanocrystal shape has been investigated for epitaxial manganese oxide (Mn3O4) nanocrystals. Mn3O4 (101) nanoplatelets and (112)-orientated nanowires have been successfully deposited on (111) and (110) SrTiO3 (STO) substrates, respectively. Under higher magnifications, the (101) platelets were found to exhibit step-like growth, spiraling outward from a local dislocation site at the Mn3O4-STO interface. Selected area electron diffraction analysis from transmission electron microscope (TEM) was carried out to determine the in-plane edge directionalities of (101) and (112) Mn3O4. We found the (101) Mn3O4 orientation to exhibit a complex in-plane epitaxial relation of Mn3O4//STO and an out-of-plane relation of Mn3O4// STO. Furthermore, lattice misorientations of 58° in-plane and 35° out-of-plane have been calculated, attributed to the shear caused by the spiral growth. For the (112) Mn3O4 nanowires, the TEM diffraction pattern indicates pyramidal cross-sections based along STO. Subsequent calculations reveal that the (112) nanowires have their long axis (c-axis) such that Mn3O4//STO. Thus the nanowires grow preferentially along its longest axis giving rise to the observed shape and anisotropic nature.