Molecular dynamics simulations of nanocrystalline copper under shock loading show an unexpected ultrahigh strength behind the shock front, with values up to twice those at low pressure. Partial and perfect dislocations, twinning, and debris from dislocation interactions are found behind the shock front. Results are interpreted in terms of the pressure dependence of both deformation mechanisms active at these grain sizes, namely dislocation-based plasticity and grain boundary sliding. These simulations, together with new shock experiments on nanocrystalline nickel, raise the possibility of achieving ultrahard materials during and after shock loading.