Mild cognitive impairment (MCI) is predicted to be a common cognitive impairment in primary health care. Early detection and appropriate management of MCI can slow the rate of deterioration in cognitive deficits. The current methods for early detection of MCI have not been satisfactory for some doctors in primary health care. Therefore, an easy, fast, accurate and reliable method for screening of MCI in primary health care is needed. This study intends to develop a decision tree clinical algorithm based on a combination of simple neurological physical examination and brief cognitive assessment for distinguishing elderly with MCI from normal elderly in primary health care. This is a diagnostic study, comparative analysis in elderly with normal cognition and those presenting with MCI. We enrolled 212 elderly people aged 60.04–79.92 years old. Multivariate statistical analysis showed that the existence of subjective memory complaints, history of lack of physical exercise, abnormal verbal semantic fluency, and poor one-leg balance were found to be predictors of MCI diagnosis (p ≤ 0.001; p = 0.036; p ≤ 0.001; p = 0.013). The decision trees clinical algorithm, which is a combination of these variables, has a fairly good accuracy in distinguishing elderly with MCI from normal elderly (accuracy = 89.62%; sensitivity = 71.05%; specificity = 100%; positive predictive value = 100%; negative predictive value = 86.08%; negative likelihood ratio = 0.29; and time effectiveness ratio = 3.03). These results suggest that the decision tree clinical algorithm can be used for screening of MCI in the elderly in primary health care.