This study aimed to estimate the prevalence of leisure-time physical activity and investigate its association with contextual characteristics of the social and physical environment in different socioeconomic statuses, using a household survey in Belo Horizonte, Minas Gerais State, Brazil (2008-2009). Leisure-time physical activity was measured by the International Physical Activity Questionnaire; and the social and physical environment by scales arising from perception of neighborhood attributes. Multilevel logistic regression analysis was performed separately for each socioeconomic status stratum. The overall prevalence of leisure-time physical activity was 30.2%, being 20.2% amongst participants of low socioeconomic status, 25.4% in the medium and 40.6% in the high socioeconomic status group. A greater perception of social cohesion was associated with increased leisure-time physical activity only amongst participants of the lowest socioeconomic status even after adjusting for individual characteristics. The results demonstrate the importance of social cohesion for the promotion of leisure-time physical activity in economically disadvantaged groups, supporting the need to stimulate interventions for enhancing social relationships in this population.