Fear of predators fundamentally shapes the ecology of prey species and drives both inter- and intra-specific interactions. Extensive research has examined the consequences of predation risk from large carnivores on the behavior of wild ungulate prey species. However, many large carnivores not only hunt wild prey but also depredate domestic livestock, especially in pastoralist systems where livestock share land and resources with large carnivores. Northern Tanzania is a hotspot for human-carnivore conflict driven by livestock depredation and interactions are particularly severe between African lions (Panthera leo) and pastoralist cattle (Bos taurus). In this ecosystem, we explored the degree to which pastoralist cattle exhibited anti-predator behaviors during their daily grazing routines. Using focal animal sampling, we compared two typical anti-predator behaviors, vigilance and grouping, among cattle in village rangelands with high and low background depredation rates. We found that cattle in high risk village rangelands formed 21.2% larger groups than cattle in low risk village rangelands. Interestingly, cattle in low risk village rangelands spent 68.4% more time vigilant than cattle in high risk village rangelands. These patterns were influenced significantly by the time of day: as sunset approached, cattle in low risk village rangelands spent more time vigilant and cattle in high risk village rangelands formed larger groups. These results suggest that pastoralist cattle exhibit anti-predator strategies that vary both spatially and temporally, and that such strategies might help livestock optimally trade-off the costs and benefits of anti-predator behavior across timescales (i.e., the risk allocation hypothesis). We discuss the implications of our results for husbandry techniques that might reduce behavioral costs associated with cattle anti-predator behaviors and help increase tolerance for lions and other large carnivores. These improvements are critical to human-carnivore coexistence given the prevalence of pastoralism globally and the rising potential for conflict with large carnivores such as lions.