An increasing number of industrial applications need superstrength steels. It is known that refined grains and nanoscale precipitates can increase strength. The hardest martensitic steel reported to date is C0.8 steel, whose nanohardness can reach 11.9 GPa through incremental interstitial solid solution strengthening. Here we report a nanograined (NG) steel dispersed with nanoscale precipitates which has an extraordinarily high hardness of 19.1 GPa. The NG steel (shock-compressed Armox 500T steel) was obtained under these conditions: high strain rate of 1.2 μs−1, high temperature rise rate of 600 Kμs−1 and high pressure of 17 GPa. The mean grain size achieved was 39 nm and reinforcing precipitates were indexed in the NG steel. The strength of the NG steel is expected to be ~3950 MPa. The discovery of the NG steel offers a general pathway for designing new advanced steel materials with exceptional hardness and excellent strength.