The interpretation of the depositional environment, provenance, and paleoclimate provides important information for understanding the formation and distribution of petroleum systems. The trace element and rare earth element (REE) concentrations and the heavy mineral distribution in upper Paleozoic sedimentary rocks in the Linxing area, northeastern Ordos Basin, were determined to reconstruct the paleoenvironment. The samples show clear light REE enrichment, although the degree of enrichment is generally poor. Redox proxies indicate that most of the samples were deposited in relatively dysoxic-oxic conditions. A warm and humid climate prevailed during deposition of the Benxi–Xiashihezi Formations, whereas extremely dry climate also occurred during Benxi Formation and Taiyuan Formation deposition. Shiqianfeng Formation deposition occurred in a completely dry climate. The increase in ΣREE concentrations and the decrease in the Sr/Ba ratios above the Benxi Formation indicate a rapid increase in terrigenous clastic input and sea-level fall, which was related to Permian tectonic movement. Bivariate plot diagrams show mixed felsic-basic source influences for all the formations, with the Shanxi Formation displaying certain influences from acidic sources. From late Carboniferous to early Permian, the Daqingshan uplift was the primary provenance. Subsequently, the Yinshan paleocontinent became a more important factor in the main provenance as it was being continuously uplifted.