With the aging process, brain functions, such as attention, memory, and cognitive functions, degrade over time. In a super-aging society, the alteration of neural activity owing to aging is considered crucial for interventions for the prevention of brain dysfunction. The complexity of temporal neural fluctuations with temporal scale dependency plays an important role in optimal brain information processing, such as perception and thinking. Complexity analysis is a useful approach for detecting cortical alteration in healthy individuals, as well as in pathological conditions, such as senile psychiatric disorders, resulting in changes in neural activity interactions among a wide range of brain regions. Multi-fractal (MF) and multi-scale entropy (MSE) analyses are known methods for capturing the complexity of temporal scale dependency of neural activity in the brain. MF and MSE analyses exhibit high accuracy in detecting changes in neural activity and are superior with regard to complexity detection when compared with other methods. In addition to complex temporal fluctuations, functional connectivity reflects the integration of information of brain processes in each region, described as mutual interactions of neural activity among brain regions. Thus, we hypothesized that the complementary relationship between functional connectivity and complexity could improve the ability to detect the alteration of spatiotemporal patterns observed on electroencephalography (EEG) with respect to aging. To prove this hypothesis, this study investigated the relationship between the complexity of neural activity and functional connectivity in aging based on EEG findings. Concretely, MF and MSE analyses were performed to evaluate the temporal complexity profiles, and phase lag index analyses assessing the unique profile of functional connectivity were performed based on the EEGs conducted for young and older participants. Subsequently, these profiles were combined through machine learning. We found that the complementary relationship between complexity and functional connectivity improves the classification accuracy among aging participants. Thus, the outcome of this study could be beneficial in formulating interventions for the prevention of age-related brain dysfunction.