(1) Background: Knee osteoarthritis (KOA) and aging are associated with high sarcopenia risk; sarcopenia may further affect outcomes after total knee replacement (TKR). Elastic resistance exercise training (RET) limits muscle attenuation in older adults. We aimed to identify the effects of post-TKR elastic RET on lean mass (LM) and functional outcomes in overweight and obese older women with KOA by using the brief International Classification of Functioning, Disability and Health Core Set for osteoarthritis (Brief-ICF-OA). (2) Methods: Eligible women aged ≥60 years who had received unilateral primary TKR were randomly divided into an experimental group (EG), which received postoperative RET twice weekly for 12 weeks, and a control group (CG), which received standard care. The primary and secondary outcome measures were LM and physical capacity, respectively, and were linked to the Brief-ICF-OA. The assessment time points were 2 weeks prior to surgery (T0) and postoperative at 1 month (T1; before RET) and 4 months (T2; upon completion of RET) of follow-up. An independent t test with an intention-to-treat analysis was conducted to determine the between-group differences in changes of outcome measures at T1 and T2 from T0. (3) Results: Forty patients (age: 70.9 ± 7.3 years) were randomly assigned to the EG (n = 20) or CG (n = 20). At T2, the EG exhibited significantly greater improvements in leg LM (mean difference (MD) = 0.86 kg, p = 0.004) and gait speed (MD = 0.26 m/s, p = 0.005) compared with the CG. Furthermore, the EG generally obtained significantly higher odds ratios than the CG for treatment success for most Brief-ICF-OA categories (all p < 0.001). Conclusions: Early intervention of elastic RET after TKR yielded positive postoperative outcomes based on the Brief-ICF-OA. The findings of this study may facilitate clinical decision-making regarding the optimal post-TKR rehabilitation strategy for older women with KOA.