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, little is known about (i) how they develop; (ii) how they are influenced by grazing; or (iii) the extent to which intraspecific interactions dictate them. 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 has lateral roots extending well beyond its canopy. We therefore hypothesized that mesquite distributions would be (a) random on grazed areas and clustered on protected areas; and (b) 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.