Grain refinement is an effective approach to improve mechanical properties of conventionally-manufactured high entropy alloys (HEAs). Additive manufacturing of HEAs is a new materials challenge and increasing reports are available for exploring the optimal processing parameters and post-manufacturing treatments to advance the physical and mechanical properties of additively-manufactured (AM) HEAs. At the current stage of the development of AM HEAs, it is necessary to investigate the significance of grain refinement on their mechanical properties and structures. In the present study, a CoCrFeNi HEA is manufactured by a laser powder-bed fusion technique using pre-alloyed HEA powders on which grain refinement was conducted by high-pressure torsion for up to 8 turns under 6 GPa at room temperature. The results from nanoindentation and Vickers microhardness testing demonstrate high strain hardening capability and increased plasticity, thus potentially high ductility, in the nanostructured AM CoCrFeNi HEA. X-ray diffraction analysis demonstrates the structural evolution with decreasing crystallite size, increasing microstrain and expanding lattice parameter with grain refinement in the HEA. The structural changes justify the estimation by nanoindentation of the rate-controlling mechanism of the grain boundary-mediated dislocation activity for the nanostructured AM HEA. This study provides advantages of nanostructuring for current developments in the AM technology of HEAs.