Introduction: Overweight and obesity are important public health problems in preschoolers because most eating and physical activity habits are established during childhood. The purpose of this study was to investigate the prevalence of overweight and obesity among Tehranian preschoolers using different standard criteria and to determine their relation with physical fitness. Materials and Methods: This cross-sectional study was conducted with 381 preschoolers, aged 5 to 6 years. Anthropometric, health-related and motor fitness tests were assessed in all children. Results: Based on IOTF reference, 7.36% (CI: 0.037–0.111) and 4.73% (CI: 0.017–0.078) of boys and 11.51% (CI: 0.070–0.160) and 10.99%(CI: 0.066–0.154) of girls were overweight and obese, respectively. Significant correlations were found between 20m sprint test, predicted VO2max and most of the anthropometric indices in boys and between modified sit-ups, predicted VO2max and most of the anthropometric indices in girls. Conclusions: These findings emphasize the relatively high prevalence of overweight and obesity in both sexes and show that overweight and obesity were limiting factors for fitness performance levels. Overweight and obesity were indicative of poor physical fitness in both genders. Overweight and obese children, compared to their underweight and normal-weight counterparts, demonstrate inferior performance in most motor and health-related fitness parameters.