Objectives: To investigate the long-term effects on cognition and brain function after installing treadmill workstations in offices for 13 months. Methods: Eighty healthy overweight or obese office workers aged 40–67 years were individually randomized to an intervention group, receiving a treadmill workstation and encouraging emails, or to a control group, continuing to work as usual. Effects on cognitive function, hippocampal volume, prefrontal cortex (PFC) thickness, and circulating brain-derived neurotrophic factor (BDNF) were analyzed. Further, mediation analyses between changes in walking time and light-intensity physical activity (LPA) on changes in BDNF and hippocampal volume between baseline and 13 months, and multivariate analyses of the baseline data with percentage sitting time as the response variable, were performed. Results: No group by time interactions were observed for any of the outcomes. In the mediation analyses, positive associations between changes in walking time and LPA on changes in hippocampal volume were observed, although not mediated by changes in BDNF levels. In the multivariate analyses, a negative association between percentage sitting time and hippocampal volume was observed, however only among those older than 51 years of age. Conclusion: Although no group by time interactions were observed, our analyses suggest that increased walking and LPA may have positive effects on hippocampal volume and that sedentary behavior is associated with brain structures of importance for memory functions. Trial Registration: www.ClinicalTrials.gov as NCT01997970.