Brain electroencephalography (EEG), the complex, weak, multivariate, nonlinear, and nonstationary time series, has been recently widely applied in neurocognitive disorder diagnoses and brain-machine interface developments. With its specific features, unlabeled EEG is not well addressed by conventional unsupervised time-series learning methods. In this article, we handle the problem of unlabeled EEG time-series clustering and propose a novel EEG clustering algorithm, that we call mwcEEGc. The idea is to map the EEG clustering to the maximum-weight clique (MWC) searching in an improved Fréchet similarity-weighted EEG graph. The mwcEEGc considers the weights of both vertices and edges in the constructed EEG graph and clusters EEG based on their similarity weights instead of calculating the cluster centroids. To the best of our knowledge, it is the first attempt to cluster unlabeled EEG trials using MWC searching. The mwcEEGc achieves high-quality clusters with respect to intracluster compactness as well as intercluster scatter. We demonstrate the superiority of mwcEEGc over ten state-of-the-art unsupervised learning/clustering approaches by conducting detailed experimentations with the standard clustering validity criteria on 14 real-world brain EEG datasets. We also present that mwcEEGc satisfies the theoretical properties of clustering, such as richness, consistency, and order independence.