We studied the response of vegetation and vertebrate assemblages to fire and grazing, and their interacting effects, in Eucalyptus woodland in north-eastern Australia. In this vegetation type, many pastures remain free of cattle grazing due to the occurrence of a native shrub poisonous to livestock. Vegetation (floristic data and 22 habitat variables) and vertebrate fauna (birds, mammals, reptiles) were sampled in 29 standardized 50 × 50-m quadrats in the 2001 wet season, representing four treatments: sites burnt recently (within 2 y) and grazed by cattle (4–8 ha per livestock unit); sites unburnt (last burnt >2 y ago) and grazed; sites burnt recently and ungrazed; and unburnt and ungrazed sites. Fire and grazing had a significant influence on vegetation: both grazing and fire reduced ground cover (fire in grazed sites 51–23%, fire in ungrazed sites 68–39%) and increased the cover of forbs (8% in burnt and grazed sites, 3% if ungrazed) and tussock grasses (20% in grazed and unburnt sites and 5% when ungrazed). Grazing caused a shift in floristic composition from the perennial hummock grass Trioda pungens to tussock grasses (e.g. Aristida spp., Enneapogon spp.), forbs (e.g. Phyllanthus spp.) and shrubs (e.g. Acacia spp.). Of the vertebrate groups, birds responded more to fire effects (9 species), reptiles to grazing effects (6 species) and mammals to the interaction (2 species). Species reacted to increases in bare ground (e.g. crested pigeon Ocyphaps lophotes, hooded robin Melanodryas cucullatus, Ctenophorus nuchalis) and to the dominant ground cover (e.g. Ctenotus pantherinus) or change in vegetation architecture (e.g. singing honeyeater Lichenostomus virescens, variegated fairy-wren Malurus lamberti). The clearest example of an interacting effect was the cycle of complementary dominance between the rodents Pseudomys delicatulus and P. desertor, the latter's post-fire recovery becoming more muted in sites where cattle grazed (modelled time for population recovery twice as long as in ungrazed sites).