Background: Data on the effect of physical activity intensity on depression is scarce. We investigated the prospective association between intensity of leisure-time exercise and risk of depressive symptoms among Japanese workers. Methods: The participants were 29,052 employees (24,653 men and 4,399 women) aged 20 to 64 years without psychiatric disease including depressive symptoms at health checkup in 2006–2007 and were followed up until 2014–2015. Details of leisure-time exercise were ascertained via a questionnaire. Depressive states were assessed using a 13-item questionnaire. Multivariable-adjusted hazard ratio of depressive symptoms was estimated using Cox regression analysis. Results: During a mean follow-up of 5.8 years with 168,203 person-years, 6,847 workers developed depressive symptoms. Compared with workers who engaged in no exercise during leisure-time (0 MET-hours per week), hazard ratios (95% confidence intervals) associated with >0 to <7.5, 7.5 to <15.0, and ≥15.0 MET-hours of leisure-time exercise were 0.88 (0.82–0.94), 0.85 (0.76–0.94), and 0.78 (0.68–0.88) among workers who engaged in moderate-intensity exercise alone; 0.93 (0.82–1.06), 0.82 (0.68–0.98), and 0.83 (0.71–0.98) among workers who engaged in vigorous-intensity exercise alone; and 0.96 (0.80–1.15), 0.80 (0.67–0.95), and 0.76 (0.66–0.87) among workers who engaged in both moderate- and vigorous-intensity exercise with adjustment for age, sex, lifestyles, work-related and socioeconomic factors, and body mass index. Additional adjustment for baseline depression score attenuated the inverse association, especially among those who engaged in moderate-intensity exercise alone. Conclusions: The results suggest that vigorous-intensity exercise alone or vigorous-intensity combined with moderate-intensity exercise would prevent depressive symptoms among Japanese workers.