Ab initio calculations are performed to investigate the electronic structure of Fe2NbAl full-Heusler alloy as well as the non-stoichiometric Fe1.75X0.25NbAl and Fe2Y0.25Nb0.75Al (X, Y = Cr, Mn, Co) alloys. The thermoelectric properties of these alloys are computed using Boltzmann transport formalism. Fe2NbAl alloy is found to exhibit a semiconductor structure with an indirect band gap of 0.3 eV along the I"-X high symmetry line. However, Fe1.75X0.25NbAl (X = Cr, Mn, Co) and Fe2Y0.25Nb0.75Al (Y = Cr, Co) are found to be metallic, whereas Fe2Mn0.25Nb0.75Al is semiconductor with a band gap of 0.2 eV at I"-point. The p-type of Fe2NbAl alloy shows a maximum Seebeck coefficient of 220 mu V/K at 800 K, whereas the n-type shows a peak of 280 mu V/K at 150 K. The maximum power factor reaches 12 and 51 x 10(-3) W/mK(2) at hole concentrations of similar to 1.60 x 10(21) and 1.45 x 10(-3) cm(-3) for the p-type material and about 18 and 42 x 10(-3) W/mK(2) at electron concentrations of similar to 1.65 x 10(21) and 1.6 x 10(-3) cm(-3) for the n-type at 300 and 800 K, respectively. Alloying Fe2NbAl with Cr, Mn, and Co at Fe and Nb sites leads to an appreciable increase in the PF values of the non-stoichiometric alloys, which indicates higher efficiencies and potential thermoelectric applications.