Changes in functional brain connectivity (FBC) may indicate how lifestyle modifications can prevent the progression to dementia; FBC identifies areas that are spatially separate but temporally synchronized in their activation and is altered in those with mild cognitive impairment (MCI), a prodromal state between healthy cognitive aging and dementia. Participants with MCI were randomly assigned to one of five study arms. Three times per week for 20-weeks, participants performed 30-min of (control) cognitive training, followed by 60-min of (control) physical exercise. Additionally, a vitamin D(3) (10,000 IU/pill) or a placebo capsule was ingested three times per week for 20-weeks. Using the CONN toolbox, we measured FBC change (Post-Pre) across four statistical models that collapsed for and/or included some or all study arms. We conducted Pearson correlations between FBC change and changes in physical and cognitive functioning. Our sample included 120 participants (mean age: 73.89 ± 6.50). Compared to the pure control, physical exercise (model one; p-False Discovery Rate (FDR) < 0.01 & < 0.05) with cognitive training (model two; p-FDR =  < 0.001), and all three interventions combined (model four; p-FDR =  < 0.01) demonstrated an increase in FBC between regions of the Default-Mode Network (i.e., hippocampus and angular gyrus). After controlling for false discovery rate, there were no significant correlations between change in connectivity and change in cognitive or physical function. Physical exercise alone appears to be as efficacious as combined interventional strategies in altering FBC, but implications for behavioral outcomes remain unclear.