ZnO is a high melting point, high charge carrier mobility semiconductor with potential as a thermoelectric material, but its high thermal conductivity κ is the limiting factor for increasing the thermoelectric figure of merit ZT. Here, we demonstrate that doping ZnO with heavy elements can significantly enhance ZT. Indium doping leads to ultralow κ [similar] 3 W m−1 K−1 and a high power factor α2σ [similar] 1.230 × 10−3 W m−1 K−2, yielding ZT1000K [similar] 0.45 that is [similar]80% higher than non-nanostructured In–Zn–O alloys. Although Bi doping also yields a high Seebeck coefficient of α300K [similar] 500 μV K−1, Bi segregation, grain growth and defect complexing are unfavorable for increasing ZT. Thus, besides increased impurity scattering of phonons, the concurrence of nanostructuring and charge carrier concentration control is key to ZT enhancement. Our results open up a new means to realize high ZT thermoelectric nanomaterials based on ZnO.