African pastoralists are undergoing significant changes in livelihood strategies, from predominantly mobile pastoralism to agro-pastoralism in which both livestock raising and cultivation of crops are practiced, to agro-pastoralism combined with wage labor and petty trade. These changes often result in fixed settlements or a process known as sedentarization. Previous research indicates that sedentarization and increased climate variability are prominent forces shaping livelihood opportunities and constraints in East Africa, but the effects of these co-occurring processes have yet to be investigated. This paper develops theory, using qualitative data collected in Morogoro and Tanga Regions of Tanzania, explaining the relationships between climate variability, pastoral sedentarization, livelihood outcomes, and resulting nutritional status. We observed that the co-occurring processes of increased climate variability and sedentarization among pastoralists in these regions have dramatic impacts on communities’ economic prosperity, health status, and nutritional outcomes. Due to risks associated with climate and sedentarization, land tenure policies that allow continued practice of highly mobile livelihood strategies, namely, legal recognition of collective land rights, should be adopted.