Fine-grained Ti-doped FeVSb half-Heusler alloys were synthesized by combining mechanical alloying and spark plasma sintering and their thermoelectric properties were investigated with an emphasis on the influences of Ti doping and phase purity. It was found that substituting V with Ti can change the electrical transport behavior from n-type to p-type due to one less valence electron of Ti than V, and the sample with nominal composition FeV0.8Ti0.4Sb exhibits the largest Seebeck coefficient and the maximum power factor. By optimizing the sintering temperature and applying annealing treatment, the power factor is significantly improved and the thermal conductivity is reduced simultaneously, resulting in a ZT value of 0.43 at 500 °C, which is relatively high as for p-type half-Heusler alloys containing earth-abundant elements.