The aim was to comprehensively examine school-based tobacco policy status, implementation and students' perceived smoking at school in regard to gender-specific differences in smoking behavior. We conducted a multilevel-based study to assess two-level effects for smoking among 2350 grades three to six students in 26 randomly selected elementary schools in southern Taiwan. A series of multilevel models were analyzed separately for male and female students. The school-level variables appear to be related to smoking behavior in male students. Among males, the risk of ever-smoking was significantly associated with those schools without antitobacco health education activities or curricula [adjusted odds ratio (aOR) = 6.23, 95% confidence interval (CI): 2.55-15.24], with a high perceived smoking rate (aOR = 3.08, 95% CI: 1.41-6.72) and located in a mountainous region (aOR = 2.53, 95% CI: 1.15-5.58). The risk of ever-smoking among females was significantly associated with those schools without antitobacco activities or curricula (aOR = 3.10, 95% CI: 1.27-7.55). As compared with female counterparts, the specific school that the male students attended had a positive significant effect on the risk of being ever-smokers. The findings suggest that effective tobacco policy implementation should be considered in elementary schools that are currently putting children at the greatest risk for cigarette smoking, especially in regard to male students.