Many grasslands in the Chihuahuan Desert have transformed to shrublands dominated by creosotebush (Larrea tridentata). Grassland restoration efforts have been directed at controlling creosotebush by applying herbicide over large spatial scales. However, we have a limited understanding of how landscape-scale restoration affects biodiversity. We examined whether restoration treatments in southern New Mexico, USA have influenced the community structure of lizards, which are sensitive to shrub encroachment. We compared lizard community structure on 21 sites treated with herbicide from 7-29 years ago with paired references matched by geomorphology, soils, and elevation. To examine mechanisms underlying responses to restoration, we tested whether the abundance of a grassland specialist, Aspidoscelis uniparens, depended on time since treatment, treatment area and isolation, and local habitat quality. Because lizards use rodent burrows as habitat, we tested whether community structure and A. uniparens abundance depended on the abundance of the keystone rodent, Dipodomys spectabilis. Treatments had reduced shrub cover and increased grass cover compared to references. Lizard community composition differed strongly between plots, with four species responding to treatments. Divergence in community composition between treatment-reference pairs was greatest for old treatments (=22 years), and community composition was influenced by D. spectabilis. In particular, the abundance of A. uniparens was greatest on old treatments with a high density of D. spectabilis. Overall, our results demonstrate lizard community structure responds to grassland restoration efforts, and keystone species can shape restoration responses. Reestablishment of keystone species may be a critical constraint on the recovery of animal biodiversity after habitat restoration.