A healthy lifestyle is an important focus in today's society. The physical benefits of regular exercise are abundantly clear, but physical fitness is also associated with better cognitive performance. How these two factors together relate to characteristics of the brain is still incompletely understood. By applying mathematical concepts from 'network theory', insights in the organization and dynamics of brain functioning can be obtained. We test the hypothesis that neural network organization mediates the association between cardio respiratory fitness (i.e. VO₂ max) and cognitive functioning. A healthy cohort was studied (n = 219, 113 women, age range 41-44 years). Subjects underwent resting-state eyes-closed magneto-encephalography (MEG). Five artifact-free epochs were analyzed and averaged in six frequency bands (delta-gamma). The phase lag index (PLI) was used as a measure of functional connectivity between all sensors. Modularity analysis was performed, and both within and between-module connectivity of each sensor was calculated. Subjects underwent a maximum oxygen uptake (VO₂ max) measurement as an indicator of cardio respiratory fitness. All subjects were tested with a commonly used Dutch intelligence test. Intelligence quotient (IQ) was related to VO₂ max. In addition, VO₂ max was negatively associated with upper alpha and beta band modularity. Particularly increased intermodular connectivity in the beta band was associated with higher VO₂ max and IQ, further indicating a benefit of more global network integration as opposed to local connections. Within-module connectivity showed a spatially varied pattern of correlation, while average connectivity did not show significant results. Mediation analysis was not significant. The occurrence of less modularity in the resting-state is associated with better cardio respiratory fitness, while having increased intermodular connectivity, as opposed to within-module connections, is related to better physical and mental fitness.