This study aims to analyze the association between perceived environmental factors and leisure-time physical activity (PA) among adolescents of both genders. Data were collected in autumn of 2011 from 866 adolescents (412 girls and 454 boys) 12- to 18-years-old, from four Portuguese cities. Perception of environmental factors was assessed by Assessing Levels of Physical Activity and Fitness (ALPHA) questionnaire (Spittaels et al., 2010, IJBNPA). PA was assessed by a questionnaire that evaluated PA during leisure-time and participants were assigned into the following categories: sedentary; low active; moderate active; and very active. Boys presented higher levels of structured PA, frequency and intensity of PA, and level of sport competition than girls (p < 0.001). Distance to local facilities (p = 0.001 for girls; p < 0.001 for boys) and home environment (p = 0.004 for girls; p = 0.015 for boys) were negatively associated with PA. Total, cycling and walking infrastructures (p < 0.001), as well as cycling and walking network (p = 0.049) and connectivity (p = 0.034) showed a positive association with PA in boys. Analysis of variance showed significant differences between girls' PA regarding aesthetics (p = 0.013), study environment (p = 0.023), home environment (p = 0.014) and whether it is pleasant or not (p = 0.023). Differences between boys' PA were observed for distance to local facilities (p = 0.003), total, cycling and walking infrastructures (p < 0.001) and home environment (p = 0.002). This study results support that some environmental factors are associated with adolescents' PA levels, with relevant differences between genders. Therefore, these gender differences must be taken into account, in order to increase levels of PA in Portuguese youth, especially in girls.