Invasive species challenge managers of natural areas. In many ecosystems, restoring and maintaining pre-historic disturbance regimes promotes native biodiversity and controls invasive plant species. We report challenges in applying patch-burn grazing to restore the ecological interaction between fire and herbivores in eastern North American tallgrass prairie. We use United States Forest Service fire behavior software and fuel models to simulate the effect of a cool-season grass invasion into tallgrass prairie. By introducing a high-moisture fuel type into the native fuelbed, tall fescue (Lolium arundinaceum Schreb. S.J. Darbyshire) creates a heterogeneous fuelbed that limits fire spread rate. Our results indicate that a high-moisture fuel type invading a high proportion of a fuelbed requires up to four times the wind speed to achieve a rate of spread similar to that in an uninvaded fuelbed. Reduced fire spread undermines restoring the natural fire regime, putting invaded grassland systems at a higher risk of succession to a woodland state. To mitigate against negative effects of high-moisture invaders on prescribed burning and ensure that fires maintain the intensity required for management goals, managers should consider the following when planning burns: Accumulate higher fuel loads by reducing herbivory or reducing fire frequency; burn earlier in the spring or later in the fall, during the dormant season of the invader; and consider alternative fire weather such as lower relative humidity, perhaps with lower wind speeds to maintain an acceptable level of complexity.