The Tarim Basin is one of the richest basins in oil and gas resources in China. The Cambrian and Middle–Upper Ordovician strata are the most important source rocks. Previous early Paleozoic thermal histories have led to varied hypotheses on the evolution of the lower Paleozoic source rocks, causing a significant impact on petroleum exploration in the basin. A new Paleozoic thermal history of the Tarim Basin was reconstructed in this article using the integrated thermal indicators of apatite and zircon (uranium-thorium)/helium ages, apatite fission tracks, and equivalent vitrinite reflectance data. The modeled results indicate that different parts of the basin experienced widely differing early Paleozoic thermal gradient evolution. The eastern and central regions of the basin experienced a decreasing thermal gradient evolution from 37 to 39C/km during the Cambrian and Ordovician to 35 to 36C/km in the Silurian, whereas the northwestern region of the basin had an increasing early Paleozoic thermal gradient evolution from 28 to 32C/km in the Cambrian to 30 to 34C/km in the Ordovician and Silurian. The Lower Cambrian thermal gradient resulted from the higher thermal conductivity of the 800- to 1000-m (2625- to 3280-ft) thickness of gypsum and salt in the Cambrian strata. The basin experienced an intracratonic phase during the late Paleozoic and a foreland basin phase during the Mesozoic and Cenozoic, with the thermal gradient decreasing to the present-day value of 20 to 25C/km. The sensitivity of thermal modeling by the best-fit method is less than 5% in our study, and the differences of the early Paleozoic thermal gradient evolution in different regions of the basin may result in differential maturation of lower Paleozoic source rocks. The maturity histories of the source rocks, modeled based on the new thermal histories, indicate that the lower Paleozoic source rocks in most areas of the basin matured rapidly and reached the late mature to dry-gas stage during the Paleozoic but experienced slower maturation during the Mesozoic and Cenozoic. These new data on the Paleozoic thermal history and lower Paleozoic source rock maturity histories of the Tarim Basin provide new insights to guide oil and gas exploration of the basin.