TiC-doped NaAlH4 complex hydride was prepared by hydrogenating of ball-milled NaH/Al mixture in the presence of 5 mol% TiC powder, and its hydrogen storage behaviors and microstructure were investigated. It is found that TiC is a good catalyst for the reversible hydriding/dehydriding process of NaAlH4 at moderate temperatures by reducing the decomposition temperature and improving the hydriding/dehydriding kinetics. The hydrogen desorption capacity of 5 mol% TiC-doped NaAlH4 is 4.6 wt% at 165 °C and its average dehydriding rate in the first 30 min reaches 0.107 wt%/min. X-ray diffraction analyses show that the size of crystal grains of the composites is reduced by ball-milling, and is then increased rapidly in the first hydriding–dehydriding cycle. Scanning electron micrographs represent that the particle size of the ball-milled composites is quite even and averages around 50 nm. However, it changes into a widely distributed one ranging from 50 nm to 1 μm in the subsequent hydriding–dehydriding cycles. DSC measurement indicates that the doping of TiC can lower the dehydriding temperatures of sodium aluminum hydride.