Background: Studies on non-pharmacological strategies for improving gait performance and cognition in Parkinson’s disease (PD) are of great significance. We aimed to investigate the effect of and mechanism underlying enriched rehabilitation as a potentially effective strategy for improving gait performance and cognition in early-stage PD.Methods: Forty participants with early-stage PD were randomly assigned to receive 12 weeks (2 h/day, 6 days/week) of enriched rehabilitation (ER; n = 20; mean age, 66.14 ± 4.15 years; 45% men) or conventional rehabilitation (CR; n = 20; mean age 65.32 ± 4.23 years; 50% men). In addition, 20 age-matched healthy volunteers were enrolled as a control (HC) group. We assessed the general motor function using the Unified PD Rating Scale—Part III (UPDRS-III) and gait performance during single-task (ST) and dual-task (DT) conditions pre- and post-intervention. Cognitive function assessments included the Montreal Cognitive Assessment (MoCA), the Symbol Digit Modalities Test (SDMT), and the Trail Making Test (TMT), which were conducted pre- and post-intervention. We also investigated alteration in positive resting-state functional connectivity (RSFC) of the left dorsolateral prefrontal cortex (DLPFC) in participants with PD, mediated by ER, using functional magnetic resonance imaging (fMRI).Results: Compared with the HC group, PD participants in both ER and CR groups performed consistently poorer on cognitive and motor assessments. Significant improvements were observed in general motor function as assessed by the UPDRS-III in both ER and CR groups post-intervention. However, only the ER group showed improvements in gait parameters under ST and DT conditions post-intervention. Moreover, ER had a significant effect on cognition, which was reflected in increased MoCA, SDMT, and TMT scores post-intervention. MoCA, SDMT, and TMT scores were significantly different between ER and CR groups post-intervention. The RSFC analysis showed strengthened positive functional connectivity between the left DLPFC and other brain areas including the left insula and left inferior frontal gyrus (LIFG) post-ER.Conclusion: Our findings indicated that ER could serve as a potentially effective therapy for early-stage PD for improving gait performance and cognitive function. The underlying mechanism based on fMRI involved strengthened RSFC between the left DLPFC and other brain areas (e.g., the left insula and LIFG).