A study on spatio-temporal changes of tectonic paleostress is helpful to recognize and understand structural deformation of fold-and-thrust belt and final formation of structural trap of hydrocarbon accumulation. The observations and measures on many faults in the Tertiary as well as in the Cretaceous rocks in the Kuqa Depression, Tarim Basin, could help us to reconstruct Late Tertiary tectonic paleostress field by inversing a lot of fault-slip data. The inversion results combining with field observations showed that the direction of compressive stress underwent a change from NNW-SSE to NNW-SSE, and the Tertiary structural compression of the Kuqa Depression had two stages: NNW-SSE compressive deformation in the earlier stage and NWW-SEE compressive one in the later stage. Meanwhile, the results from varied structural belts indicated that the paleostresses had consisted each other. According to the period of hydrocarbon accumulation in the Kuqa Depression, we thought that the two stages of compressive deformation played a critical role in the final formation of structural trap, specially, the later stage of deformation supported a good situation for the trap. In addition, two possible causes of Tertiary compressive deformation were discussed in the paper.