NiTi is the most used shape-memory alloy; nonetheless, a lack of understanding remains regarding the associated structures and transitions, including their barriers. Using a generalized solid-state nudged elastic band method implemented via density-functional theory, we detail the structural transformations in NiTi relevant to shape memory: those between a body-centered orthorhombic (bco) ground state and a newly identified stable austenite ("glassy" B2-like) structure, including energy barriers (hysteresis) and intermediate structures (observed as a kinetically limited R phase), and between martensite variants (bco orientations). All results are in good agreement with available experiment. We contrast the austenite results to those from the often-assumed, but unstable B2. These high- and low-temperature structures and structural transformations provide much needed atomic-scale detail for transitions responsible for NiTi shape-memory effects.