Recent data revealed that adolescent obesity appeared to be a rising problem in Cyprus. However, there is a scarcity of published data regarding fitness-related parameters, which could contribute for the presence of obesity in Cyprus' adolescence population. The aim of the current study was to investigate the association between adolescent obesity, body composition, and fitness levels. A total of 270 high school students volunteered to participate in this cross-sectional study. Body mass and height were assessed in order to calculate body mass index, while body fat percentage was calculated by using bioelectrical impedance analysis. Physical fitness parameters were assessed through a battery of field tests. Body fat was inversely associated with cardiorespiratory fitness levels, sprint and jumping performance, as well as with the frequency of physical education class sessions per week (p<0.05). The adolescents with high body fat were found to exhibit significant reductions in all the fitness related parameters (p<0.05), except with the arm strength (p>0.05). This study is the first to uncover an inverse association between high body fat and fitness-related parameters among a sample of adolescents in Cyprus. These data can be used in order to develop effective interventions aiming to counterbalance obesity and improve the overall health and the quality of life of adolescents.