Browsing by introduced cattle (Bos taurus) and rabbits (Oryctolagus cuniculus) can limit the recruitment of some arid zone tree and shrub species. In a study conducted at the Arid Recovery Reserve, Roxby Downs, SA, we aimed to quantify initial recruitment changes in shrubs after the removal of cattle and rabbits and the re-introduction of locally extinct fauna. The presence and abundance of seedlings was measured at groves of seven native perennial shrubs over 6 years under four browsing treatments: (1) ‘reserve-reintroductions’ [re-introduced greater stick-nest rats (Leporillus conditor), burrowing bettongs (Bettongia lesueur) and greater bilbies (Macrotis lagotis)], (2) ‘reserve-no browsers’, (3) ‘pastoral-stocked’ (rabbits and cattle), and (4) ‘pastoral-destocked’ (rabbits). Recruitment of mulga (Acacia aneura F.Muell. ex Benth.), silver cassia (Senna artemisioides subsp. petiolaris Randell) and sandhill wattle (Acacia ligulata A.Cunn. ex Benth.) was significantly greater in the two browsing regimes inside the Reserve than in the two pastoral regimes. The number of recruits of these three species declined at ‘pastoral-destocked’ and ‘pastoral-stocked’ sites but increased at ‘reserve-reintroductions’ and ‘reserve-no browsers’ sites from 2001 to 2006. Narrow-leaf hopbush (Dodonaea viscose (L.) Jacq.) showed a trend towards increased recruitment at sites in both browsing regimes inside the Reserve, but decreased recruitment at sites in both pastoral regimes. Native plum (Santalum lanceolatum R.Br.), native apricot (Pittosporum phylliraeoides orth. var. DC.) and bullock bush (Alectryon oleifolius (Desf.) S.T.Reynolds) exhibited no significant difference in recruitment between the four browsing regimes within the study timeframe. These results suggest that excluding rabbits and stock may benefit the germination and survival of mulga, silver cassia and sandhill wattle. To date, re-introduced native herbivores at low numbers have not been found to negatively affect the recruitment or growth rate of the seven perennial plant species studied.