Atomic substitution in alloys can efficiently scatter phonons, thereby reducing the thermal conductivity in crystalline solids to the "alloy limit." Using In0.53Ga0.47As containing ErAs nanoparticles, we demonstrate thermal conductivity reduction by almost a factor of 2 below the alloy limit and a corresponding increase in the thermoelectric figure of merit by a factor of 2. A theoretical model suggests that while point defects in alloys efficiently scatter short-wavelength phonons, the ErAs nanoparticles provide an additional scattering mechanism for the mid-to-long-wavelength phonons.©2006 The American Physical Society