ZnO is a promising high figure-of-merit (ZT) thermoelectric material for power harvesting from heat due to its high melting point, high electrical conductivity σ, and Seebeck coefficient α, but its practical use is limited by a high lattice thermal conductivity κ(L). Here, we report Al-containing ZnO nanocomposites with up to a factor of 20 lower κ(L) than non-nanostructured ZnO, while retaining bulklike α and σ. We show that enhanced phonon scattering promoted by Al-induced grain refinement and ZnAl(2)O(4) nanoprecipitates presages ultralow κ ∼ 2 Wm( -1) K(-1) at 1000 K. The high α∼ -300 μV K(-1) and high σ ∼ 1-10(4) Ω(-1 )m(-1) result from an offsetting of the nanostructuring-induced mobility decrease by high, and nondegenerate, carrier concentrations obtained via excitation from shallow Al donor states. The resultant ZT ∼ 0.44 at 1000 K is 50% higher than that for the best non-nanostructured counterpart material at the same temperature and holds promise for engineering advanced oxide-based high-ZT thermoelectrics for applications.