Increasing cover by woody vegetation, prevalent in semiarid savanna rangelands throughout the world, is a degrading process attributed to the grazing impact as a major causal factor. We studied grazing effects on savanna vegetation dynamics under alternative stocking strategies with a spatially explicit grid-based simulation model grounded in Kalahari (southern Africa) ecology. Plant life histories were modeled for the three major life forms: perennial grasses, shrubs, annuals. We conducted simulation experiments over a range of livestock utilization intensities for three alternative scenarios of small scale grazing heterogeneity, and two alternative strategies: fixed stocking versus adaptive stocking tracking herbage production. Additionally, the impact of the duration of the management planning horizon was studied, by comparing community response and mean stocking rates after 20 and 50 years. Results confirmed a threshold behavior of shrub cover increase: at low, subcritical utilization intensity little change occurred; when utilization intensity exceeded a threshold, shrub cover increased drastically. For both stocking strategies, thresholds were highly sensitive to grazing heterogeneity. At a given critical utilization intensity, the long term effect of grazing depended on the level of grazing heterogeneity: whereas under low heterogeneity, shrub cover remained unchanged, a large increase occurred under highly heterogeneous grazing. Hence, information on spatial grazing heterogeneity is crucial for correct assessment of the impact of livestock grazing on vegetation dynamics, and thus for the assessment of management strategies. Except for the least heterogeneous grazing scenario, adaptive stocking allowed a more intensive utilization of the range without inflating the risk of shrub cover increase. A destabilizing feedback between rainfall and herbage utilization was identified as the major cause for the worse performance of fixed compared to adaptive stocking, which lacks this feedback. Given the usually high grazing heterogeneity in semiarid rangelands, adaptive stocking provides a management option for increasing herbage utilization and thus returns of livestock produce without increasing degradation risks.