Monitoring physical fitness (fitness) and identifying, since the beginning, possible determinants in youth could be useful to preserve health and avoid morbidities in adulthood. The main objective of this study is to provide details on the fitness levels of a sample of adolescents living in the Southern area of Italy and describe its associations with biological/genetic, socio-cultural/environmental, and lifestyle (physical activity/sedentariness, alcohol/smoking, meal patterns/habits) factors. The study was conducted within the Adolescence Surveillance System for Obesity Prevention (ASSO) project, funded by the Italian Ministry of Health and examining adolescents’ lifestyle in relation to obesity. Fitness measures were collected through the ASSO-fitness tests battery (FTB) and examined in relation to 79 selected possible influencing factors, which were collected through a web-based questionnaire included in the ASSO-NutFit software. Logistic regression analyses were performed to assess associations, with ORs and 95% CIs estimated as crude and adjusted. A total of 919 participants were initially recruited, but fitness data were collected for 544 students aged 13–19 (68% M, 32% F). Fitness level was low for 14.2% of the students, medium for 67.8%, and high for 18.0%. The independent determinants of low physical fitness in our sample of adolescents were included in the biological/genetic and physical activity/sedentariness dimensions: female gender (Adj OR 8.33, CI 2.08–33.33), obesity (Adj OR 1.97, CI 1.10–9.22), practicing sport less than 3 h/week (Adj OR 6.09, CI 1.63–22.72), practicing sport with strength/speed as prevalent biomotor ability (Adj OR 8.97, CI 1.43–56.19), using PC/internet for more than 3 h/day (Adj OR 4.46, CI 1.17–16.98). Drinking alcohol was instead a protective factor. This study confirms that females and obese individuals need more attention in the interventions aimed at increasing fitness levels. It suggests that local actions should be implemented with the aim of increasing sport practices and reducing sedentary time spent in front of PC/internet. The focus should be particularly addressed to sports with strength or speed as dominant biomotor abilities.