Tree and shrub abundance has increased in many grasslands causing changes in ecosystem carbon and nitrogen pools that are related to patterns of woody plant distribution. However, with regard to spatial patterns of shrub proliferation, little is known about how they are influenced by grazing or the extent to which they are influenced by intraspecific interactions. We addressed these questions by quantifying changes in the spatial distribution of Prosopis velutina (mesquite) shrubs over 74 years on grazed and protected grasslands. Livestock are effective agents of mesquite dispersal and mesquite plants have lateral roots extending well beyond the canopy. We therefore hypothesized that mesquite distributions would be random on grazed areas mainly due to cattle dispersion and clustered on protected areas due to decreased dispersal and interspecific interference with grasses; and that clustered or random distributions at early stages of encroachment would give way to regular distributions as stands matured and density-dependent interactions intensified. Assessments in 1932, 1948, and 2006 supported the first hypothesis, but we found no support for the second. In fact, clustering intensified with time on the protected area and the pattern remained random on the grazed site. Although shrub density increased on both areas between 1932 and 2006, we saw no progression toward a regular distribution indicative of density-dependent interactions. We propose that processes related to seed dispersal, grass–shrub seedling interactions, and hydrological constraints on shrub size interact to determine vegetation structure in grassland-to-shrubland state changes with implications for ecosystem function and management.