The lattice thermal conductivity (κ_{ω}) is a key property for many potential applications of compounds. Discovery of materials with very low or high κ_{ω} remains an experimental challenge due to high costs and time-consuming synthesis procedures. High-throughput computational prescreening is a valuable approach for significantly reducing the set of candidate compounds. In this article, we introduce efficient methods for reliably estimating the bulk κ_{ω} for a large number of compounds. The algorithms are based on a combination of machine-learning algorithms, physical insights, and automatic ab initio calculations. We scanned approximately 79,000 half-Heusler entries in the AFLOWLIB.org database. Among the 450 mechanically stable ordered semiconductors identified, we find that κ_{ω} spans more than 2 orders of magnitude—a much larger range than that previously thought. κ_{ω} is lowest for compounds whose elements in equivalent positions have large atomic radii. We then perform a thorough screening of thermodynamical stability that allows us to reduce the list to 75 systems. We then provide a quantitative estimate of κ_{ω} for this selected range of systems. Three semiconductors having κ_{ω}<5  Wm^{−1} K^{−1} are proposed for further experimental study.