Background: Although an impaired cognitive status in patients with coronary artery disease (CAD) is not rare, the neurophysiological and clinical indicators of mild cognitive impairment (MCI) have been insufficiently investigated so far. Methods: EEG and neuropsychological testing as well as clinical examination were performed on 122 patients with CAD, who were divided into two groups, those with MCI (n = 60; mean age 57.4 ± 5.81 years) and those without MCI (n = 62; mean age 57.0 ± 5.04 years). Binary logistic regression was used to identify the relationship between EEG and clinical variables and the probability of MCI. Results: Higher theta/alpha ratios, theta1 rhythm power with closed eyes in the frontal and occipital areas of the left hemisphere, and alpha2 rhythm power with eyes open in the frontal areas of the right hemisphere were associated with an increased risk for MCI in CAD patients. A low educational level, type 2 diabetes mellitus, and severe coronary lesions according to the SYNTAX Score (≥23 points) increased the risk for MCI as well. Conclusions: The findings of our study show that a theta activity increase in frontal and occipital sites, as well as high theta/alpha ratios, may be considered as the earliest EEG markers of vascular cognitive disorders.