Livestock grazing is a commonly cited factor contributing to shrub encroachment in savannas and grasslands. Patterns of woody plant proliferation are known to influence rates of erosion and spread of disturbance and are of practical importance to livestock management with regard to forage distribution and abundance. However, the effects of grazing on woody plant population dynamics and stand structure are poorly understood, owing to a paucity of long-term, spatially-explicit data. We explored the spatial patterns of distribution and recruitment for velvet mesquite (Prosopis velutina) using field surveys spanning 74 years (1932, 1948, and 2006) on areas grazed by livestock since the late 1800s and protected from livestock since 1932. Univariate analyses with Ripley’s K and neighborhood density functions (NDF) revealed mesquite plants were randomly distributed in 1932. In 1948, following 16 years of protection from livestock, plants on the protected area were clustered at all distances (1 to 20m), while mesquite on the grazed area were clustered at short distances (1 to 4m) only. In 2006, mesquite on the protected area remained clustered at all distances, with a marked peak in clustering at short distances (1 to 4m), whereas mesquite on the grazed area were randomly distributed. Bivariate analyses with Ripley’s K and NDF indicated that juvenile mesquite plants (<1m height) were significantly clustered around adult plants from 2 to 5m on the protected area in 2006; but there were no significant patterns of association between juveniles and adults on the grazed area through time. Previous analyses revealed that spatial autocorrelation in mesquite density did not deviate from random on the grazed area, whereas associations on the protected area became increasingly positive. Grazing influenced recruitment-driven changes in population structure from 1932 to 2006 and protection from livestock facilitated formation of high density shrub clusters and open areas generating high spatial heterogeneity.