This cross-sectional study evaluated the relationships between anthropometric and aerobic fitness (rate of perceived exertion [RPE] and predicted maximal oxygen uptake [VO2max]) among 228 participants (age: 23.78±4.42 years). RPE and predicted VO2max were determined during the cycle ergometer exercise test. Data were also obtained for height, weight, body mass index (BMI), hip and waist (WC) circumferences. Data analysis revealed VO2max is correlated with WC (r=-0.571), weight (r=-0.521), waist-to-height ratio (WHtR) (r=-0.516), waist-to-hip ratio (WHR) (r=-0.487), and BMI (r=-0.47) in men, while, in women with WC (r=-0.581), weight (r=-0.571), WHtR (r=-0.545), BMI (r=-0.545), WHR (r=-0.473), and height (r=-0.287) (all P<0.05). Regression analysis showed WC was a significant predictor for VO2max in men and women (r 2=32.6% vs. 33.7%). The receiver operating characteristic curve of WC showed 0.786 and 0.831 for men and women, respectively. WC or abdominal obesity is the strongest predictor for VO2max, which is an indicator of aerobic fitness in Malaysian adults.