The Byzantine - Islamic transition (7th-8th centuries CE) in the desert-edge Palaestina Tertia is examined using faunal remains recovered from archaeological sites in the Negev. Archaeozoological analyses suggest sharp differences between Late Byzantine and Early Islamic animal economies, especially in herding patterns and the exploitation of wildlife resources. These differences are suggested to reflect both cultural and land ownership changes following the Arab conquest, against the backdrop of climatic change. The archaeozoological record thereby provides independent evidence to the rise and fall of societal complexity in this marginal region.