In this paper, the observation of LO-phonon progressions in the low temperature (4.2 K) photoluminescence excitation spectra of different types of colloidal NCs is reported. The strength of the exciton-LO-phonon coupling at 4.2 K, as reflected by the Huang–Rhys parameter S, increases from CdSe QDs (S = 0.8–1.0) to Type-I1/2 CdTe/CdSe HNCs (S = 1.5), and from these to Type-II CdTe/CdSe HNCs (S = 2.9). This trend is explained by the decrease in the electron–hole wave function overlap that accompanies the gradual increase in the CdSe volume fraction in the HNCs. The decrease in the electron–hole overlap increases the exciton polarization, which in turn enhances the exciton-LO-phonon coupling via the Fröhlich interaction. The results provide novel insights into the nature of spatially indirect exciton transitions and show that compositional control of semiconductor heteronanocrystals can be used as a very effective tool to tailor the exciton–phonon coupling strength of nanoscale excitons.