The introduction and eradication of alien invasive plant species potentially alters feeding and spatial ecology of wild primates. We investigated whether the removal of an important dietary resource for wild chacma baboons ( Papio hamadryas ursinus ), black wattle ( Acacia mearnsii ), from a nature reserve would result in longer daily path lengths (DPLs) and greater movement toward other resources, specifically alternative black wattle stands outside the reserve, agricultural plots, and sleeping and geophagy sites. We fitted a juvenile male baboon with a self-releasing GPS collar to track the focal troop’s movements on Wildcliff Nature Reserve and adjacent properties, located in the Western Cape, South Africa, from January 25, 2010 to January 18, 2011. During this time, Working for Water, an environmental conservation initiative of the South African Department of Water Affairs, removed black wattle from the baboons’ home range. We estimated monthly home range (5.30–20.58 km 2 ) and DPL (1.7–11.7 km) and quantified the baboons’ use of five dominant vegetation types. Our vegetation use-availability analysis indicated that the troop preferred black wattle, Afromontane forests, and, to a lesser extent, pasture, but used agricultural plots and fynbos less than expected by availability. With increasing black wattle removal in the core area, the troop traveled further toward distant sources of black wattle, using sleeping sites out of their core area to accommodate such long day journeys. A general linear model indicated that movement to black wattle stands, as well as changing sleeping sites, day length, and both spring and winter seasons all significantly increased DPL. We suggest the influence that alien invasive species and their eradication has on ranging behavior should be a consideration in primate conservation and management policies.