Body mass index (BMI; weight (kg)/height (m)2) is commonly used to measure general adiposity. However, evidence of its appropriateness for males and females remains inconsistent. We aimed to identify the most appropriate sex-specific power value that height should be raised to in the formula and the value that would make it achieve height independency and body fatness dependency. We randomly assigned UK Biobank participants recruited in the United Kingdom between 2006 and 2010 (n = 489,873; mean age = 56.5 years; 94.2% White) to training and testing sets (80%:20%). Using height raised to the power of −50.00 to 50.00, we identified the optimal power value that either minimized correlation with height or maximized correlation with body fat percentage, using age-adjusted correlations. The optimal power values for height were 1.77 for males and 1.39 for females. The new formulas resulted in 4.5% of females and 2.4% of males being reclassified into a different BMI category. The formulas did not show significant improvement (in terms of area under the receiver operating characteristic curve, sensitivity, and specificity) in identifying individuals with excessive body fat percentage or in predicting risk of all-cause mortality. Therefore, the conventional BMI formula is still valuable in research and disease screening for both sexes.