(1) Objectives: We aimed to identify clusters of physical frailty and cognitive impairment in a population of older primary care patients and correlate these clusters with their associated comorbidities. (2) Methods: We used a latent class analysis (LCA) as the clustering technique to separate different stages of mild cognitive impairment (MCI) and physical frailty into clusters; the differences were assessed by using a multinomial logistic regression model. (3) Results: Four clusters (latent classes) were identified: (1) highly functional (the mean and SD of the “frailty” test 0.58 ± 0.72 and the Mini-Mental State Examination (MMSE) test 27.42 ± 1.5), (2) cognitive impairment (0.97 ± 0.78 and 21.94 ± 1.95), (3) cognitive frailty (3.48 ± 1.12 and 19.14 ± 2.30), and (4) physical frailty (3.61 ± 0.77 and 24.89 ± 1.81). (4) Discussion: The comorbidity patterns distinguishing the clusters depend on the degree of development of cardiometabolic disorders in combination with advancing age. The physical frailty phenotype is likely to exist separately from the cognitive frailty phenotype and includes common musculoskeletal diseases.