Brain functional connectivity (FC) network, estimated with resting-state functional magnetic resonance imaging (RS-fMRI) technique, has emerged as a promising approach for accurate diagnosis of neurodegenerative diseases. However, the conventional FC network is essentially low-order in the sense that only the correlations among brain regions (in terms of RS-fMRI time series) are taken into account. The features derived from this type of brain network may fail to serve as an effective disease biomarker. To overcome this drawback, we propose extraction of novel high-order FC correlations that characterize how the low-order correlations between different pairs of brain regions interact with each other. Specifically, for each brain region, a sliding window approach is first performed over the entire RS-fMRI time series to generate multiple short overlapping segments. For each segment, a low-order FC network is constructed, measuring the short-term correlation between brain regions. These low-order networks (obtained from all segments) describe the dynamics of short-term FC along the time, thus also forming the correlation time series for every pair of brain regions. To overcome the curse of dimensionality, we further group the correlation time series into a small number of different clusters according to their intrinsic common patterns. Then, the correlation between the respective mean correlation time series of different clusters is calculated to represent the high-order correlation among different pairs of brain regions. Finally, we design a pattern classifier, by combining features of both low-order and high-order FC networks. Experimental results verify the effectiveness of the high-order FC network on disease diagnosis. Hum Brain Mapp 37:3282–3296, 2016. © 2016 Wiley Periodicals, Inc.