First principles density functional theory studies have been carried out to investigate the hydrogen interactions in Ti-doped NaAlH4 (001) and (100) surfaces. In both surfaces, Ti was found to energetically favor the interstitial sites formed by three neighboring AlH4- units and interact directly with them. The resulting local structure corresponds to a formula of TiAl3Hx with x = 12 before hydrogen desorption starts. The hydrogen desorption energies from many positions of TiAl3Hx are reduced considerably as compared with that from the corresponding clean, undoped NaAlH4 surfaces. The almost invariant local environment surrounding Ti during dehydrogenation makes the TiAl3Hx complex a precursor state for the formation of experimentally observed TiAl3. The importance of the complex has been explored by analyzing the structures and energetics accompanying hydrogen desorption from the complex and from the neighboring AlH4- units. The TiAl3Hx has extended effects beyond the locally reducing hydrogen desorption energy. It facilitates low-energy hydrogen desorption by either transferring hydrogen to the TiAl3Hx complex or reducing hydrogen desorption energy in the neighboring AlH4- by linking these AlH4- units with the complex structure. The possible mechanisms for forming octahedral AlH63- were also identified in the vicinity of TiAl3Hx. Desorbing hydrogen atoms between Ti and Al atoms causes a symmetrical expansion of Ti-Al bonds and leads to the formation of octahedral AlH63-.