Severe plastic deformation techniques including high-pressure torsion and equal channel angular pressing have been widely used to refine coarse-grained materials to produce nanocrystalline and ultrafine-grained materials, or manipulate the microstructure of nanocystalline materials for superior mechanical properties. This paper overviews severe plastic deformation induced structural and mechanical property evolutions on bulk nanocrystalline metals, mainly in a nanocrystalline Ni-20%Fe (mass fraction) alloy with a face-centred cubic (fcc) structure processed by high-pressure torsion to different strain values. The structural evolution and mechanical property evolution at different strain values were studied. Comprehensive characterizations on structural evolution during deformation indicate that: (1) grain growth occurred via grain rotation, and is accompanied with changes in dislocation density and twin density; (2) there is a significant grain size effect on deformation induced twinning and de-twinning. There exists an optimum grain size range for the formation of deformation twins. Outside of this grain size range the de-twinning process will dominate to annihilate existing twins; (3) different types of dislocation-twin boundary (TB) interactions occurred during deformation. Dislocation density plays an important role in dislocation-TB interactions. In a twinned grain with a low dislocation density, a dislocation may react with a TB to fully or partially penetrate the TB or to be absorbed by the TB via different dislocation reactions. In a twinned grain with a high dislocation density, dislocations tangle with each other and are pinned at the TBs, leading to the accumulation of dislocations at the TBs and raising the local strain energy. In order to release the stress concentration, stacking faults and secondary twins formed by partial dislocation emissions from the other side of the TB; (4) atom probe tomography investigation reveals that C and S atoms, which are the major impurities in the Ni-Fe alloy and segregated at grain boundaries (GBs) of the as-deposited material, migrated from disappearing GBs to the remaining GBs during high-pressure torsion. Investigation on structure-hardness relationship of the Ni-Fe alloy reveals that: strain hardening and strain softening occurred at different deformation stages. Dislocation density evolution plays a major role in the hardness evolution, while other structural evolutions, including twin density and grain size evolutions, play minor roles in the hardness evolution.