Since their discovery around a century ago, the structure and chemistry of the multi-functional half-Heusler semiconductors have been studied extensively as three component systems. The elemental groups constituting these ternary compounds with the nominal formula XYZ are well established. From the very same set of well-known elements we explore a phase space of quaternary double ($XXY_2Z_2$, $X_2YYZ_2$, and $X_2Y_2ZZ$), triple ($X_2XY_3Z_3$) and quadruple ($X_3XY_4Z_4$) half-Heusler compositions which 10 times larger in size. Using a reliable, first-principles thermodynamics methodology on a selection of 347 novel compositions, we predict 127 new stable quaternary compounds, already more than the 89 reported almost exhaustively for ternary systems. Thermoelectric performance of the state-of-the-art ternary half-Heusler compounds are limited by their intrinsically high lattice thermal conductivity ($kappa_{L}$). In comparison to ternary half-Heuslers, thermal transport in double half-Heuslers is dominated by low frequency phonon modes with smaller group velocities and limited by disorder scattering. The double half-Heusler composition Ti$_2$FeNiSb$_2$ was synthesized and confirmed to have a significantly lower lattice thermal conductivity (factor of 3 at room temperature) than TiCoSb, thereby providing a better starting point for thermoelectric efficiency optimization. We demonstrate a dependable strategy to assist the search for low thermal conductivity half-Heuslers and point towards a huge composition space for implementing it. Our findings can be extended for systematic discovery of other large families of multi-component intermetallic semiconductors.