Advances in the synthesis and self-assembly of nanocrystals have enabled researchers to create a plethora of different nanoparticle superlattices. But while many superlattices with complex types of translational order have been realized, rotational order of nanoparticle building blocks within the lattice is more difficult to achieve. Self-assembled superstructures with atomically coherent nanocrystal lattices, which are desirable due to their exceptional electronic and optical properties, have been fabricated only for a few selected systems. Here, we combine experiments with molecular dynamics (MD) simulations to study the self-assembly of heterostructural nanocrystals (HNCs), consisting of a near-spherical quantum dot (QD) host decorated with a small number of epitaxially grown gold nanocrystal (Au NC) "patches". Self-assembly of these HNCs results in face-centered-cubic (fcc) superlattices with well-defined orientational relationships between the atomic lattices of both QD hosts and Au patches. MD simulations indicate that the observed dual atomic coherence is linked to the number, size, and relative positions of gold patches. This study provides a strategy for the design and fabrication of NC superlattices with large structural complexity and delicate orientational order.