Systematic ab-initio structure simulations have been used to explore the high-pressure behavior of nitinol (NiTi) at zero temperature. Our crystal structure prediction and first principles calculations reveal that the known B19 phase is dynamically unstable, an orthorhombic structure (Pbcm) and a face centered cubic B32 structure (Fd-3m) become stable above ~4 and 29 GPa, respectively. The newly-predicted, highest-pressure, B32 phase is composed of two interpenetrating diamond structures, with structural topology that is quite distinct from that of the other phases of NiTi. Interestingly, the B32 phase shows unusual semiconducting characteristic as a result of its unique band structure and the nature of 3d orbitals localization, whose expected synthesis pressure is accessible to current experimental techniques.