Various ab initio approaches to the band structure of ANiSn and ACoSb half-Heusler compounds (A = Ti, Zr, Hf) are compared and their consequences for the prediction of thermoelectric properties are explored. Density functional theory with the generalized-gradient approximation (GGA), as well as the hybrid density functional HSE06 and ab initio many-body perturbation theory in the form of the GW(0) approach, are employed. The GW(0) calculations confirm the trend of a smaller band gap (0.75 to 1.05 eV) in ANiSn compared to the ACoSb compounds (1.13 to 1.44 eV) already expected from the GGA calculations. While in ANiSn materials the GW(0) band gap is 20% to 50% larger than in HSE06, the fundamental gap of ACoSb materials is smaller in GW(0) compared to HSE06. This is because GW(0), similar to PBE, locates the valence band maximum at the L point of the Brillouin zone, whereas it is at the Gamma point in the HSE06 calculations. The differences are attributed to the observation that the relative positions of the d levels of the transition metal atoms vary among the different methods. Using the calculated band structures and scattering rates taking into account the band effectivemasses at the extrema, the Seebeck coefficients, thermoelectric power factors, and figures of merit ZT are predicted for all six half-Heusler compounds. Comparable performance is predicted for the n-type ANiSn materials, whereas clear differences are found for the p-type ACoSb materials. Using the most reliable GW(0) electronic structure, ZrCoSb is predicted to be the most efficientmaterial with a power factor of up to 0.07W/(K-2 m) at a temperature of 600 K. We find strong variations among the different ab initio methods not only in the prediction of the maximum power factor and ZT value of a given material, but also in comparing different materials to each other, in particular in the p-type thermoelectric materials. Thus we conclude that the most elaborate, but also most costly GW(0) method is required to perform a reliable computational search for the optimum material.