A lower dietary protein intake has been associated with muscle mass loss, a decline in physical performance and more mobility limitations over time in old age. Current guidelines for protein intake advise ≥ 0.8 g/kg body weight (BW)/d, while experts propose a higher intake for older adults (1.0–1.2 g/kg BW/d), irrespective of sex. It is unknown whether the association between protein intake and loss of muscle mass is different for men and women, and whether there is an optimal protein intake to prevent this loss. Therefore, we investigated the shape of the association between protein intake and change in appendicular lean mass (aLM) over 3 years in community-dwelling older adults, separately for men and women. Data of men (n = 935) and women (n = 1061) aged 70–81 years and participating in the Health, Aging and Body Composition study were used. Dietary protein intake, measured in 1998/1999 using a food frequency questionnaire, was expressed in daily grams of protein per kg adjusted BW (g/kg aBW/d) by using healthy instead of actual BW. aLM was assessed by dual-energy X-ray absorptiometry at baseline and after 3 years. Restricted cubic spline functions with 3 knots in linear regression models were used as well as linear regression analyses. The fit of both models was compared using the likelihood ratio test. All analyses were stratified by sex and adjusted for demographics, lifestyle factors, chronic conditions, height and baseline aLM. Mean (SD) protein intake was 70.8 (26.2) g in men and 61.0 (22.5) g in women, or 0.93 (0.36) and 0.95 (0.36) g/kg aBW/d, respectively. Over 3 years, mean loss of aLM was 0.61 (1.16) kg in men and 0.35 (0.95) kg in women. In both men and women, the likelihood ratio was not significant (P = 0.57 and 0.67, respectively), indicating that the spline regression model did not fit the data better than the linear regression model. In men, the linear model showed no association between protein intake and change in aLM (adjusted B per 0.1 g/kg aBW/d = 18.1, P = 0.34). In women, a higher protein intake was associated with a smaller loss of aLM (adjusted B per 0.1 g/kg aBW/d = 34.5, P = 0.017). This study suggests a linear association between protein intake and 3-year loss of aLM in older women; however, no association was found in older men. Future studies into sex differences in associations with other physical outcomes are needed. For both sexes, an optimal protein intake could not be detected.