Brain complexity estimated using sample entropy and multiscale entropy (MSE) has recently gained much attention to compare brain function between diseased or neurologically impaired groups and healthy control groups. Using resting-state functional magnetic resonance imaging (rfMRI) blood oxygen-level dependent (BOLD) signals in a large cohort (n = 967) of healthy young adults, the present study maps neuronal and functional complexities estimated by using MSE of BOLD signals and BOLD phase coherence connectivity, respectively, at various levels of the brain’s organization. The functional complexity explores patterns in a higher dimension than neuronal complexity and may better discern changes in brain functioning. The leave-one-subject-out cross-validation method is used to predict fluid intelligence using neuronal and functional complexity MSE values as features. While a wide range of scales was selected with neuronal complexity, only the first three scales were selected with functional complexity. Fewer scales are advantageous as they preclude the need for long BOLD signals to calculate good estimates of MSE. The presented results corroborate with previous findings and provide a baseline for other studies exploring the use of MSE to examine changes in brain function related to aging, diseases, and clinical disorders.