The aim of this cross-sectional study was to identify individual, social, and environmental contributors (mediators) to individual- and area-level differences in leisure-time physical activity across socio-economic groups. A two-stage stratified sampling design was used to recruit 20–65 year old adults (N = 2194) living in 154 census collection districts of Adelaide, Australia (overall response rate: 12%). Participants completed two surveys six months apart (response rate on the second survey: 83%). Individual-level socio-economic status (SES) was assessed using self-report measures on educational attainment, household income, and household size. Area-level SES was assessed using census data on median household income and household size for each selected census district. Bootstrap generalized linear models were used to examine associations between SES, potential mediators, and leisure-time physical activity. The product-of-coefficient test was used to estimate mediating effects. All SES measures were independently associated with potential individual and social mediators of the SES-activity relationships. Individual- and area-level income was also associated with perceived neighborhood attributes. Self-efficacy and social support for physical activity explained virtually all of the differences in physical activity across educational attainment groups. Physical barriers to walking and access to public open space contributed in part to the explanation of differences in recreational walking across income groups. Yet, self-efficacy and social support were the key mediators of the observed relationships between individual- and area-level income and physical activity. This study suggests that in order to increase physical activity participation in the more disadvantaged segments of the population, comprehensive, multilevel interventions targeting activity-related attitudes and skills as well as social and physical environments are needed.