Parasitism and other stressors are ubiquitous in nature but their effects on animal behaviour can be difficult to identify. We investigated the effects of nematode parasitism and other indicators of physiological impairment on the sequential complexity of foraging and locomotion behaviour among wild Japanese macaques (Macaca fuscata yakui). We observed all sexually mature individuals (n = 28) in one macaque study group between October 2007 and August 2008, and collected two faecal samples/month/individual (n = 362) for parasitological examination. We used detrended fluctuation analysis (DFA) to investigate long-range autocorrelation in separate, binary sequences of foraging (n = 459) and locomotion (n = 446) behaviour collected via focal sampling. All behavioural sequences exhibited long-range autocorrelation, and linear mixed-effects models suggest that increasing infection with the nodular worm Oesophagostomum aculeatum, clinically impaired health, reproductive activity, ageing and low dominance status were associated with reductions in the complexity of locomotion, and to a lesser extent foraging, behaviour. Furthermore, the sequential complexity of behaviour increased with environmental complexity. We argue that a reduction in complexity in animal behaviour characterizes individuals in impaired or 'stressed' states, and may have consequences if animals cannot cope with heterogeneity in their natural habitats.