Objective To explore the association between change in physical activity levels and fruit and vegetable consumption and changes in self-reported overall health and mental health, of residents living in deprived English communities. Design Household survey conducted in 2002 and repeated in 2004. Setting Thirty-nine deprived UK communities in areas participating in the New Deal for Communities (NDCs), a major government funded community development initiative. Participants Ten thousand four hundred and nineteen residents in NDC areas and neighbouring comparator areas. Main results Overall levels of physical activity and fruit and vegetable consumption are low but a large positive change in diet or levels of physical activity is associated with a significant change in mental health (2.86 and 2.71, respectively: P < 0.01). Smaller, but also statistically significant, changes were found in physical health (0.07 and 0.05, P < 0.01). Specific dimensions of mental health which showed a large change in association with lifestyle change were those associated with 'peacefulness' and 'happiness'. Conclusions These findings suggest that, for residents of these neighbourhoods, positive lifestyle changes such as increasing physical activity levels and increase in fruit and vegetable consumption are associated with positive changes in mental health.