This study examined which of the identified health, psychological, social and environmental mediators could most effectively explain the socio-economic status (SES)-based differences in participation in exercise among elderly Japanese. The candidates for mediators were composed based on the socio-ecological model. A representative sample of people 65 years and older living in two areas with different residential SES in Tokyo, Japan produced 739 effective participants. The intensity of exercise was evaluated based on whether the participants exercise for 30 minutes or longer twice a week, or for 20 minutes or longer three times a week. SES was evaluated by education and income. Mediators were assessed through four dimensions: (a) health, (b) psychological status, (c) social relations and (d) environmental context. As a result, SES's indirect effect through the mediators was evaluated using a multiple mediator model. The influence of both education and income on exercise was mediated by self-efficacy for exercise and social support for exercise. Self-efficacy for exercise had the strongest effect, while social support for exercise explained more of the income differences affecting participation in exercise than it did regarding educational differences. Self-efficacy for exercise may have the strongest effect as a mediator, which would explain the differences in participation in exercise among elderly Japanese based on education and income.