The thermoelectric properties of 54 different group 4 half-Heusler (HH) alloys have been studied from first principles. Electronic transport was studied with density functional theory using hybrid functionals facilitated by the k⋅p method, while the temperature-dependent effective potential method was used for the phonon contributions to the figure of merit ZT. The phonon thermal conductivity was calculated including anharmonic phonon-phonon, isotope, alloy, and grain-boundary scattering. HH alloys have an XYZ composition, and those studied here are in the group 4-9-15 (Ti,Zr,Hf)(Co,Rh,Ir)(As,Sb,Bi) and group 4-10-14 (Ti,Zr,Hf)(Ni,Pd,Pt)(Ge,Sn,Pb). The electronic part of the thermal conductivity was found to significantly impact ZT and thus the optimal doping level. Furthermore, the choice of functional was found to significantly affect thermoelectric properties, particularly for structures exhibiting band alignment features. The intrinsic thermal conductivity was significantly reduced when alloy and grain-boundary scattering were accounted for, which also reduced the spread in thermal conductivity. It was found that sublattice disorder on the Z-site, i.e., the site occupied by group 14 or 15 elements, was more effective than X-site substitution, occupied by group 4 elements. The calculations confirmed that ZrNiSn, ZrCoSb, and ZrCoBi based alloys display promising thermoelectric properties. A few other n-type and p-type compounds were also predicted to be potentially excellent thermoelectric materials, given that sufficiently high charge carrier concentrations can be achieved. This study provides insight into the thermoelectric potential of HH alloys and casts light on strategies to optimize the thermoelectric performance of multicomponent alloys.