The mechanical performance and microstructures of a CoCrNi medium-entropy alloy (MEA) and NCoCrNi, alloyed with 0.5 at% N, after high pressure torsion (HPT) and subsequent annealing treatments in a temperature range of 150–1000 °C were investigated. The introduction of N results in a reduction of grain size by 40 % and ∼10–15 % increased hardness and bending strength after HPT. Both materials showed strain hardening and plasticity after HPT even at these strength levels over 1500 MPa which is induced by the saturated nanocrystalline state. Annealing at intermediate temperatures of 300–500 °C resulted in an additional increase of hardness and strength by ∼20–40 %, compared to the HPT deformed state. This effect was ∼10 % more pronounced in the nitrogen alloyed CoCrNi that also showed better thermal stability. However, the increase in strength after 500 °C annealing was accompanied by a drastic loss of ductility in both materials.