Objective: Quantitative EEG power has not been as effective in discriminating between healthy aging and Alzheimer's disease as conventional biomarkers. But EEG coherence has shown promising results in small samples. The overall aim was to evaluate if EEG connectivity markers can discriminate between Alzheimer's disease, mild cognitive impairment, and healthy aging and to explore the early underlying changes in coherence. Methods: EEGs were included in the analysis from 135 healthy controls, 117 patients with mild cognitive impairment, and 117 patients with Alzheimer's disease from six Nordic memory clinics. Principal component analysis was performed before multinomial regression. Results: We found classification accuracies of above 95% based on coherence, imaginary part of coherence, and the weighted phase-lag index. The most prominent changes in coherence were decreased alpha coherence in Alzheimer's disease, which was correlated to the scores of the 10-word test in the Consortium to Establish a Registry for Alzheimer's Disease battery. Conclusions: The diagnostic accuracies for EEG connectivity measures are higher than findings from studies investigating EEG power and conventional Alzheimer's disease biomarkers. Furthermore, decreased alpha coherence is one of the earliest changes in Alzheimer's disease and associated with memory function. Significance: EEG connectivity measures may be useful supplementary diagnostic classifiers.