After the founding of P. R. China, land use in rural China was organized under two successive paradigms: state-directed collectivization from 1958–1984 (the Collective Era), and privatization after 1984 (the Household Land Contract Period, HLCP). Taking Nileke County of Xinjiang as a case study, this research analyzed the livelihood changes of agro-pastoralists over the two periods using quantitative household livelihood assets—financial, physical, natural, human, and social capital—as indicators. Using annual series data of the five livelihood capitals, a comprehensive livelihood assets index (CLAI) was calculated by two-stage factor analysis. Higher CLAI scores meant better living and reduced poverty for agro-pastoralists. Quantitative results were validated and detailed with semi-structured household interviews. The results showed that CLAI slightly increased during the HLCP in comparison to the Collective Era, mainly due to increases in financial and physical capital. In contrast, natural and social capital showed downward trends, indicating that alleviation of poverty came at the cost of natural resources and social justice. Natural capital was the main contributor to agro-pastoralist livelihoods during the Collective Era, but diminished and was replaced by financial capital during the HLCP. Based on the findings, we put forward policy suggestions to improve community land management and sustainable livelihoods as part of future poverty alleviation efforts.