Sodium alanate (NaAlH4) is a prototype system for storage of hydrogen in chemical form. However, a key experimental finding, that early transition metals (TMs) like Ti, Zr, and Sc are good catalysts for hydrogen release (and reuptake) whereas traditional hydrogenation catalysts like Pd and Pt are poor catalysts for NaAlH4, has so far received little attention. We performed density functional theory (DFT) calculations at the PW91 generalized gradient approximation level on Ti, Zr, Sc, Pd, and Pt interacting with the (001) surface of nanocrystalline NaAlH4, employing a cluster model of the complex metal hydride to study the initial mass transport in the dehydrogenation process. A key difference between Ti, Zr, and Sc on one hand and Pd and Pt on the other is that exchange of the early TM atoms with a surface Na ion, whereby Na is pushed on to the surface, is energetically preferred over surface absorption in an interstitial site, as found for Pd and Pt. These theoretical findings are consistent with a crucial feature of the TM catalyst being that it can be transported with the reaction boundary as it moves into the bulk, enabling the starting material to react away while the catalyst eats its way into the bulk and affecting a phase separation between a Na-rich and an Al-rich phase. Additional periodic DFT/PW91 calculations in which NaAlH4 is modeled as a slab to model dehydrogenation of larger NaAlH4 particles and which only consider adsorption and absorption of Ti suggest that Ti prefers to absorb interstitially but with only a small energy preference over a geometry in which Ti has exchanged with Na. Additional nudged elastic band calculations based on periodic DFT show only a small barrier (0.02 eV) for exchange of Ti with a surface Na atom. The mechanism inferred from the cluster calculations is therefore consistent with the slab calculations and may well be important.