The biocompatibility of NiTi shape memory alloys (SMA) has made possible applications in invasive and minimally invasive biomedical devices. The NiTi intermetallic alloy spontaneously forms a thin passive layer of TiO2, which provides its biocompatibility. The oxide layer is thought to form as Ti in the alloy reacts with oxygen. In this paper, we study the details of the oxide-alloy interface. The atomic model is the (110) NiTi surface interfaced with the (100) rutile TiO2 surface; this combination provides the best lattice match of alloy and oxide. When the interface forms, static minimisations and molecular dynamics show that there is no migration of atoms between the alloy and the oxide. In the alloy there are some notable structural relaxations. We find that a columnar structure appears in which alternating long and short Ni-Ti bonds are present in each surface and subsurface plane into the fourth subsurface layer. The oxide undergoes some structural changes as a result of terminal oxygen coordinating to Ti in the NiTi surface. The electronic structure shows that Ti3+ species are present at the interface, with Ti4+ in the bulk of the oxide layer and that the metallic character of the alloy is unaffected by the interaction with oxygen, all of which is consistent with experiment. A thermodynamic analysis is used to examine the stability of different possible structures-a perfect interface and one with Ti and O vacancies. We find that under conditions typical of oxidation and shape memory treatments, the most stable interface structure is that with Ti vacancies in the alloy surface, leaving an Ni-rich layer, consistent with the experimental findings for this interface.