Nickel-titanium (NiTi) shape memory alloys undergo relatively large recoverable inelastic deformations via a stress-induced martensitic phase transformation.  Although stress-induced phase transformations in shape memory alloys are well characterized and utilized at micrometer to meter length scales, significant opportunity exists to understand and exploit martensitic transformations at nanometer scales.  Displacive stress-induced martensitic phase transformations may constitute an ideal nanometer scale actuator, as evident in certain biological systems, such as the T4 bacteriophage.  The present work uses nanoindentation to study the fundamentals of stress-induced martensitic phase transformations in NiTi shape memory alloys.  The experimental results presented in this study are the first to show evidence of discrete forward and reverse stress-induced thermoelastic martensitic transformations in nanometer scaled volumes of material.  Shape recovery due to indentation, followed by subsequent heating, is demonstrated for indents depths in the sub 10 nm range.  The indentation results reveal that stress-induced martensitic phase transformations nucleate at relatively low stresses at nanometer scales, suggesting a fundamental departure from traditional size scale effects observed in metals deforming by dislocation plasticity.  It is also shown that the local material structure can be utilized to modify transformation behavior at nanometer scales, yielding insight into the nature of stress-induced martensitic phase transformations at small scales and providing opportunity for the design of nanometer sized NiTi actuators.