There is a wide range of individual variability in the change of body weight in response to exercise, and this variability partly depends on genetic factors. The study aimed to determine DNA polymorphisms associated with fat loss efficiency in untrained women with normal weight in response to a 12-week aerobic training program using the GWAS approach, followed by a cross-sectional study in athletes. The study involved 126 untrained young Polish women (age 21.4 ± 1.7 years; body mass index (BMI): 21.7 (2.4) kg/m2) and 550 Russian athletes (229 women, age 23.0 ± 4.1; 321 men, age 23.9 ± 4.7). We identified one genome-wide significant polymorphism (rs116143768) located in the ACSL1 gene (acyl-CoA synthetase long-chain family member 1, implicated in fatty acid oxidation), with a rare T allele associated with higher fat loss efficiency in Polish women (fat mass decrease: CC genotype (n = 122) −3.8%; CT genotype (n = 4) −31.4%; p = 1.18 × 10−9). Furthermore, male athletes with the T allele (n = 7) had significantly lower BMI (22.1 (3.1) vs. 25.3 (4.2) kg/m2, p = 0.046) than subjects with the CC genotype (n = 314). In conclusion, we have shown that the rs116143768 T allele of the ACSL1 gene is associated with higher fat loss efficiency in response to aerobic training in untrained women and lower BMI in physically active men.