Background/Objectives: Advanced Glycation End Products (AGEs) are high-molecular-weight compounds formed through non-enzymatic reactions between sugars and proteins, lipids, or nucleic acids. This study aimed to comprehensively analyze the association between the accumulation of AGEs and lower-limb muscle strength, gait speed, and balance abilities related to mobility in elderly individuals. Methods: This cross-sectional correlational study included 552 community-dwelling older adults. AGE accumulation was assessed using skin autofluorescence (SAF) measured using an AGE reader. Mobility decline factors were evaluated using the sit-to-stand (STS), gait speed (4 m walk tests), single-leg stance (SLS), and Timed Up and Go (TUG) tests. Results: A comparison of the physical function across the quartile groups revealed that the group with the highest SAF values, Q4, exhibited a general decline in STS, gait speed, SLS, and TUG performance when compared with the other groups (p < 0.001). Spearman’s correlation analysis revealed that the SAF-AGEs demonstrated significant negative correlations with STS (r = −0.211, p < 0.001), gait speed (r = −0.243, p < 0.001) and SLS (r = −0.201, p < 0.001). Additionally, TUG showed a significant positive correlation (r = 0.239, p < 0.001). In the logistic regression analysis, compared with the Q1 group, the Q4 group had significantly higher odds of low STS performance (odds ratio (OR) = 2.43, p = 0.006), slow gait speed (OR = 2.28, p = 0.002), low SLS performance (OR = 2.52, p = 0.001), and slow TUG (OR = 2.00, p = 0.035). The optimal cutoff value of the SAF for mobility decline was 3.15 (area under the curve 0.694; 95% confidence interval: 0.618–0.771). Conclusions: This study has demonstrated that higher SAF values were associated with decreased lower-limb strength, gait speed, and balance, thereby suggesting that SAF may be a useful screening tool for predicting mobility decline in older adults.