Multidomain lifestyle interventions represents a promising strategy to counteract cognitive decline in older age. Brain-derived neurotrophic factor (BDNF) is essential for experience-dependent plasticity and increases following physical exercise, suggesting that physical exercise may facilitate subsequent learning. In a randomized-controlled trial, healthy older adults (65-75 years) completed a 12-week behavioral intervention that involved either physical exercise immediately before cognitive training (n = 25; 13 females), physical exercise immediately after cognitive training (n = 24; 11 females), physical exercise only (n = 27; 15 females), or cognitive training only (n = 21; 12 females). We hypothesized that cognition would benefit more from cognitive training when preceded as opposed to followed by physical exercise and that the relationship between exercise-induced increases in peripheral BDNF and cognitive training outcome would be greater when cognitive training is preceded by physical exercise. Greater increases of plasma BDNF were associated with greater cognitive training gains on trained task paradigms, but only when such increases preceded cognitive training (ß = 0.14, 95% CI [0.04, 0.25]). Average cognitive training outcome did not differ depending on intervention order (ß = 0.05, 95% CI [-0.10, 0.20]). The study provides the first empirical support for a time-critical but advantageous role for post-exercise increases in peripheral BDNF for learning at an interindividual level in older adults, with implications for future multidomain lifestyle interventions.