Purpose: This study aimed to assess the impact of complex decongestive therapy (CDT) on proprioception, balance, light touch sensation, and two-point discrimination (2PD) in patients with lower extremity lymphedema (LLL) post-endometrial and cervical cancers. Methods: The study included 72 patients diagnosed with LLL, who were randomly assigned using a block randomization method into two groups: a study group (n = 36) receiving CDT and a control group (n = 36) receiving no intervention. Patients were assessed before and after treatment using a digital goniometer for proprioception at 15°, 45°, and 60° knee flexion angles, a single-leg balance test with eyes open and closed, and a 30-s chair-stand test for balance assessment. Sensation was evaluated using Semmes Weinstein Monofilaments for light touch sensation and an aesthesiometer for 2PD. Results: Significant improvements were observed in knee flexion at 15°, 45°, and 60° in the study group compared to the control group (p < 0.001, p < 0.001, and p < 0.001, respectively). Although there was no difference between groups in single-leg balance with eyes open (p = 0.074) and closed (p = 0.919), improvements were noted within the study group before and after treatment (p < 0.001). There was no significant difference between groups in light touch sensation, while the 2PD parameter improved in the study group (p = 0.012). Conclusions: CDT may not fully address sensory deficits in patients with LLL. Balance issues appear to worsen with lymphedema progression regardless of treatment. However, CDT shows promise in improving kinesthesia. Clinical Trial Registration: This is listed with study ID: NCT06204510.