Shape-memory alloys (SMAs) are a unique class of metal alloys that after a large deformation can, on heating, recover their original shape. In the many practical applications of SMAs, the most commonly used material is NiTi (nitinol). A full atomic-level understanding of the shape-memory effect in NiTi is still lacking, a problem particularly relevant to ongoing work on scaling down shape-memory devices for use in micro-electromechanical systems. Here we present a first-principles density functional study of the structural energetics of NiTi. Surprisingly, we find that the reported B19' structure of NiTi is unstable relative to a base-centred orthorhombic structure that cannot store shape memory at the atomic level. However, the reported structure is stabilized by a wide range of applied or residual internal stresses. We propose that the memory is stored primarily at the micro-structural level: this eliminates the need for two separate mechanisms in describing the two-way shape-memory effect.