Background: Parkinson’s disease (PD) is a neurodegenerative disease manifested by both motor and non-motor dysfunctions and co-existence of cognitive impairment and physical frailty is common. Given that research in this area is limited, a better understanding of associated factors with physical frailty could provide a focused screening method and facilitate early intervention in PD. Methods: Seventy-six patients with idiopathic PD were recruited and Fried’s criteria of physical frailty were used to group all participants. Comprehensive cognitive tests and clinical characteristics were measured, and univariate and multivariate analysis was performed to explore the relationship between clinical factors or neuropsychological functions. Results: Twenty-nine patients with PD (38%) exhibited physical frailty. Compared to PD patients without frailty, PD patients with frailty were older in age and demonstrated worse disease severity and poorer cognitive functions, including attention, executive function, memory, speech and language, and visuospatial function (p < 0.05). Further, stepwise logistic regression analysis revealed that disease severity by the Unified Parkinson’s Disease Rating Scale (UPDRS) total score (OR: 1.065; 95% CI: 1.033–1.099) and executive function (OR: 0.724; 95% CI: 0.581–0.877) were independent risk factors for predicting physical frailty (p = 0.003 and 0.002). The best cut-off points are 46 in UPDRS (sensitivity: 62.1%; specificity: 91.5%). Conclusions: Executive function impairment is an independent risk factor for the development of physical frailty with disease progression. Awareness of such comorbidity might provide a screening tool to facilitate investigation in their underlying etiology and early intervention for frailty prevention.