Abstract: Lead telluride (PbTe) is a promising medium-temperature thermoelectric material for waste heat recovery. However, intrinsic PbTe suffers from low carrier concentration, and the trade-off between electrical and thermal transport parameters hinders the improvement of thermoelectric performance. In this study, a synergistic modification strategy combining iodine (I) substitutional donor doping and carbon nanotubes (CNTs) interfacial compositing was adopted to simultaneously regulate electronic and phonon transport in the PbTe matrix. Iodine atoms substituted Te lattice sites to optimize carrier concentration, thereby boosting electrical conductivity and the power factor. Furthermore, CNTs were introduced via high-energy ball milling to construct abundant heterointerfaces. These heterointerfaces achieved dual effects: they strongly scattered phonons to reduce lattice thermal conductivity, while interfacial potential barriers triggered the carrier energy filtering effect to enhance the Seebeck coefficient, thus alleviating the trade-off between electrical and thermal properties. The results demonstrated that the optimal composition, PbTe-0.4%I-0.4%CNTs (where I in molar fraction and CNTs in mass fraction), exhibited a peak thermoelectric figure of merit of approximately 1.22 at 723 K, which is nearly six times higher than that of pristine PbTe. This work verifies that the combination of carrier concentration regulation and heterointerface engineering is an effective route to improve the thermoelectric performance of PbTe-based medium-temperature materials.