Litter decomposition determines the nutrient and carbon cycling processes and regulates nutrient return to the soil in many terrestrial ecosystems. Wood plant litter decomposition is a crucial biogeochemical process for carbon and nutrient cycling, especially in arid and nutrient-constrained ecosystems. However, the role of litter decomposition in extreme drought deserts and the determining factors remain debatable and poorly understood. The Tarim Desert Highway Shelterbelt consists of three artificial plant species that account for the majority of net primary productivity, and their litters are the major contributors to carbon and nutrient recycling. In such artificial desert shelter forests, the addition of fertilizer causes contradictory effects on litter decomposition and nutrient dynamics. This study aims to (1) examine how the addition of fertilizer affects surface litter decomposition and nutrient dynamics, and (2) determine the major factors influencing litter decomposition in arid deserts. The litterbag method was used to investigate the assimilative branches decomposition of Calligonum arborescens and Haloxylon ammodendron, and the branches decomposition of Tamarix ramosissima in the Taklimakan Desert Research Station. Filled litterbags were placed on soil surfaces at different plots in March 2013. Fertilizer addition and irrigation were implemented from March to November during the experiment. Litterbags were collected in May, July, September, and November of 2013, and in March and May of 2014. The mass remaining, elemental content (carbon, nitrogen, phosphorus, and potassium), and decomposition rates of litter were analyzed at each decomposition stage. Results showed that after 420 days of decomposition, significant differences were found among control (without fertilizer), addition of nitrogen fertilizer, and phosphorus and potassium compound fertilizer treatments. The mass remaining for the assimilative branches of C. arborescens, assimilative branches of H. ammodendron, and branches of T. ramosissima without fertilizer addition were 56.95%, 31.32%, and 50.24%, respectively. The decomposition rate of fertilizer treatments among different litters was the highest for the assimilative branches of H. ammodendron, followed by the branches of T. ramosissima, and then the assimilative branches of C. arborescens. The addition of phosphorus and potassium compound fertilizer significantly accelerated the litter decomposition rate of the three plant species, whereas nitrogen fertilizer increased the decomposition rate of the branches of T. ramosissima and restrained the decomposition rate of the assimilative branches of C. arborescens and H. ammodendron. During the decomposition process, litter nutrients presented net release patterns in the treatments without fertilizer. In contrast, the nitrogen, phosphorus, and potassium contents of the fertilizer treatments showed an accumulation-release pattern. The litter decomposition rate was determined by the initial phosphorus content and C/N and C/P ratios at the initial decomposition stage. However, the decomposition rate was controlled by the initial potassium, lignin, and cellulose contents and C/N, and lignin/N ratios at the final stage. Overall, the results suggest that the addition of fertilizer significantly changed the decomposition rate of surface litters, increased the amount of returned nutrients, and postponed the time of nutrient release. Improving soil fertility in the Tarim Desert Highway shelterbelt is essential in enhancing the quality of this valuable ecosystem. The initial litter C/N ratio is critical to surface litter decomposition in the Tarim Desert, and the initial chemical composition to surface litter decomposition rate varies at different decomposition stages.