The re-introduction paradigm is that Arabian Oryx (Oryx leucoryx) herds adjust the size of their home ranges depending on the availability of vegetation, which is directly related to rainfall. In Israel, Arabian oryx were released in two hyper-arid sites: the Arava Valley and in the Paran wilderness, belonging to the Sudanese and the Saharo–Arabian biogeographic zones, respectively. While post-release survival was similar in both, reproductive success in the Paran wilderness reintroduction site was extremely low, resulting in an acute decline of the reintroduced population over time. The hypothesis that impaired nutrition might be associated with this finding was assessed with near-infrared spectroscopy (NIRS)-aided chemistry of monthly sampled fecal pellets, used as remote sensing evidence of ingested diets, throughout a year. Fecal nitrogen (FN), used as an estimate of nutritional status, was consistently higher in the Arava. Grass was never the sole or even a major dietary component. The dietary contribution of tannin-rich browse was high and steady all year-round in the Arava and increased steadily in Paran from winter to summer, corresponding to the period of availability of Acacia raddiana pods in both regions. The oryx in Paran had a home-range that was ten-fold, compared to the Arava, suggesting less feed availability. Acacia browsing may mitigate the effects of temporal variance in primary production. Under such conditions, oryx should be preferably released in areas that support significant acacia stands.