Large-scale molecular dynamics simulations have been applied to investigate the atomistic deformation mechanisms of tensile deformation in a CrCoNi medium-entropy alloy with heterogeneous grain structures. After yielding, the heterogeneous grain structures show strong strain hardening due to grain-to-grain yielding and Masing hardening. The grain-to-grain yielding can be attributed to the various grain sizes and the different Schmidt factors. The HCP transformation and formation of hierarchical deformation nanotwins have been observed in the CrCoNi with heterogeneous grain structures due to the low stacking fault energy at cryogenic temperature. The HCP phase was found to be formed by simultaneous nucleation and propagation of intrinsic stacking faults at adjacent slip planes from grain boundaries (GBs). It was found that there is no equivalent strain partitioning between large grains and small grains in the heterogeneous grain structures, which can be attributed to that GBs of small grains can also accommodate significant shear strains due to the enhanced GB activities for small grains. While tensile strain partitioning between large grains and small grains in the heterogeneous grain structures was observed, and this tensile strain partitioning was found to become more obvious with increasing grain size ratio between large grains and small grains. The simulation results should provide insights of designing heterogeneous structures for achieving better mechanical properties. © 2019 Acta Materialia Inc.