Purpose: The existing literature has shown that the amount of sedentary time during early adolescence is low. This decrease is more pronounced among girls than boys. Therefore, the purpose of this study is to analyze high school students' exercise-related stages of change (ESC) and physical activity self-efficacy (PASE) for overcoming barriers with respect to gender, age, and school type. Research Methods: The survey method, which employed stratified sampling based on the total number of students at each school, was used to select participants (n = 393). Findings: According to the results, male students were at more advanced stages of change and had higher levels of self-efficacy for overcoming barriers than their female counterparts. The distribution of high school students across the stages of change was: inactive stages (n[subscript precontemplation, contemplation, and preparation] = 216, 54.9%) and active stages (n[subscript action and maintenance] = 177, 45.1%). Gender [ESC X[superscript 2] (4, n = 393) = 14.64, p = 0.01] and the type of school [X[superscript 2] (20, n = 393) = 39.42, p>0.05] were not significantly related to ESC. MANOVA indicated that self-efficacy was related to ESC (Pillai's Trace = 0.09, F[subscript (12,678)] = 1.92, p<0.05). On the other hand, there was no significant difference in self-efficacy based on age, gender, or school type (p>0.05). Implications for Research and Practice: The sex of students was a significant variable affecting ESC. In addition, the results indicated that lower level of ESC and less PASE exist among female students. Further research should focus on cultivating girls' exercise habits with the goal of improving exercise behavior intention and self-efficacy for overcoming barriers via stage-specific interventions.