Full-Heusler alloys with earth-abundant elements exhibit high mechanical strength and favorable electrical transport behavior, but their high intrinsic lattice thermal conductivity limits potential thermoelectric application. Here, the thermoelectric transport properties of Fe-based Full-Heusler Fe₂MAl (M = V, Nb, Ta) alloys are comprehensively investigated utilizing density functional theory. The results suggest that Fe₂NbAl exhibits exceptionally low lattice thermal conductivity due to low phonon velocities and weakly bound Nb atoms. In Fe₂NbAl, the underbonding of the Nb atoms leads large Grüneisen parameters and high anharmonic scattering rates of low-frequency acoustic phonon. Meanwhile, the high band degeneracy and large electrical conductivity lead to a maximum p-type power factor of 255.6 μW·K⁻²·cm⁻¹ at 900 K. The combination of low lattice thermal conductivity and favorable electrical transport properties leads a maximum p-type dimensionless figure of merit of 1.7. Our work indicates Fe₂NbAl, as a low-cost, environmentally friendly, is a potential high-performance p-type thermoelectric material.