Objectives: To determine the prevalence of possible sarcopenia and examine its associations with malnutrition and other related factors among community-dwelling older adults attending public primary care clinics in Malaysia. Methods: A cross-sectional study was conducted among participants aged ≥60 years from January to November 2024 in 11 public primary care clinics in Malaysia. Possible sarcopenia was determined based on handgrip strength according to the Asian Working Group for Sarcopenia 2019. Firth’s penalized likelihood logistic regression was performed to determine the associated factors. Results: A total of 551 participants were included in the analysis, of whom 51.4% had possible sarcopenia. Malay ethnicity (adjusted odds ratio [aOR] 2.17, 95% confidence interval [CI] 1.09–4.34), Indian ethnicity (aOR 2.77, 95% CI 1.05–4.34), frailty (aOR 2.31, 95% CI 1.45–3.66), being at risk of malnutrition (aOR 1.68, 95% CI 1.07–2.64), and malnutrition (aOR 3.40, 95% CI 1.08–10.70) were independently associated with higher odds of possible sarcopenia. Conversely, having previously worked in a professional occupation (aOR 0.55, 95% CI 0.32–0.96) was independently associated with lower odds of possible sarcopenia. Conclusion: Possible sarcopenia was highly prevalent among community-dwelling older adults attending public primary care clinics in Malaysia. Key independent correlates of possible sarcopenia were non-professional occupational status, Malay and Indian ethnicities, malnutrition risk or overt malnutrition and frailty. Routine primary care screening using handgrip dynamometry and frailty assessments is recommended to enable early detection and targeted interventions, focusing on nutritional support, adequate hydration, and frailty management.