Nutritional knowledge, attitudes and practice (KAP) may guide healthy meal choices. Here, nutritional KAP was compared across school students in Sabah based on locality and gender. A cross-sectional survey of students aged 15–19 years was conducted using multistage sampling. Nutritional KAP was measured via questionnaire. Anthropometric measures of weight and height were taken in person to calculate body mass index (BMI). Among the 994 participants, 80% were urban and 60% were female (mean age 16.5 ± 0.6 yr). Most were of Kadazan-Dusun (23%) ethnicity. Measured height for age Z score (HAZ) and BMI for age Z score (BAZ) differed between urban and rural students (−1.2 ± 0.8 versus −1.5 ± 0.7 for HAZ; p < 0.001; 0.2 ± 1.4 versus −0.1 ± 1.3; p = 0.02, respectively). No difference in nutritional knowledge was found, although urban students prioritized having a healthy/balanced diet (59.55% versus 48.50%, p = 0.03) and ate daily breakfast (57.4% versus 10.2%, p < 0.001) compared to rural. Females scored higher on nutritional knowledge than males (18.9 ± 2.8 vs. 18.1 ± 3.4, respectively, p = 0.0001), yet males selected more healthy/balanced foods (63.3% versus 53.3%, p = 0.041). The gap remains between nutritional KAP and translating this to healthy eating among adolescents, related to locality and gender.