Non-thermal partial crystallization in a heterogeneous or structurally unstable Zr-Cu-Al metallic glass upon deep cryogenic cycling has been firstly observed, in which the samples are cooled and heated between ambient temperature and 113K. With the increment of cryogenic cycling number, the volume fraction of nano-ordered clusters increases, which finally results in partial crystallization. Meanwhile, the amorphous phase is rejuvenated into a less relaxed state, which is caused by the internal stress during cycling. The non-thermal partial crystallization is induced by the hopping events of the atoms activated by the internal stress, which causes the less-ordered or matrix atoms to adopt more ordered states. The partial crystallization in samples can greatly plasticize the sample because of the generated composite structure, as well as more free volume in the samples. These findings provide a new method to plasticize metallic glasses, as well as a deeper understanding of microstructure change of metallic glasses upon the cryogenic treatment.