The influence of Al on the thermoelectric properties of the half-Heusler (HH) TiNiSn compound is reported. The research combined ab initio Density Functional Theory (DFT) calculations with experimental microstructure evaluation and measurements of the transport properties up to 750 K. It is shown that Al addition to the Ti sub-lattice results in an increase of the absolute value of the Seebeck coefficient and electrical resistivity in polycrystalline TiNiSn, while preserving the n-type behavior of the ternary compound, in addition to a significant reduction of the thermal conductivity. In (Ti0.99Al0.01)NiSn, upon 1% Al substitution of Ti, an improvement of 17% in the thermoelectric figure of merit (0.42 at 723 K) compared to pure TiNiSn was observed. Theoretical lattice thermal conductivity calculations are applied to shed light on the different scattering mechanisms in this class of materials. It is shown that the major contribution to the lattice thermal conductivity reduction is stimulated by the presence of Sn-rich inclusions, in addition to an influence of mass fluctuation scattering due to substitution of Ti by Al. Although it is shown that in the widely applied polycrystalline TiNiSn, an addition of the acceptor Al dopant could not fully compensate n-type electronic active defects (e.g. grain boundaries) for obtaining p-type materials, the currently reported results pave a route for thermoelectric optimization of MNiSn (M = Ti, Ni, Sn) n-type half-Heusler compounds.