Many established, but also potential future applications of NiTi-based shape memory alloys (SMA) in biomedical devices and solid-state refrigeration require long fatigue life with 107-109 duty cycles1,2. However, improving the fatigue resistance of NiTi often compromises other mechanical and functional properties3,4. Existing efforts to improve the fatigue resistance of SMA include composition control for coherent phase boundaries5-7 and microstructure control such as precipitation8,9 and grain-size reduction3,4. Here, we extend the strategy to the nanoscale and improve fatigue resistance of NiTi via a hybrid heterogenous nanostructure. We produced a superelastic NiTi nanocomposite with crystalline and amorphous phases via severe plastic deformation and low-temperature annealing. The as-produced nanocomposite possesses a recoverable strain of 4.3% and a yield strength of 2.3 GPa. In cyclic compression experiments, the nanostructured NiTi micropillars endure over 108 reversible-phase-transition cycles under a stress of 1.8 GPa. We attribute the enhanced properties to the mutual strengthening of nanosized amorphous and crystalline phases where the amorphous phase suppresses dislocation slip in the crystalline phase while the crystalline phase hinders shear band propagation in the amorphous phase. The synergy of the properties of crystalline and amorphous phases at the nanoscale could be an effective method to improve fatigue resistance and strength of SMA.