Physical exercise (PE) has been shown to improve brain function via multiple neurobiological mechanisms promoting neuroplasticity. Cognitive exercise (CE) combined with PE may show an even greater effect on cognitive function. Brain-derived neurotrophic factor (BDNF) is important for neuroplastic signaling, may reduce with increasing age, and is confounded by fitness. The source and physiological role of human peripheral blood BDNF in plasma (pBDNF) is thought to differ from that in serum (sBDNF), and it is not yet known how pBDNF and sBDNF respond to PE and CE. A training intervention study in healthy older adults investigated the effects of acute (35 min) and prolonged (12 weeks, 30 sessions) CE and PE, both alone and in combination, on pBDNF and sBDNF. Cross-sectional associations between baseline pBDNF, sBDNF and cardiorespiratory fitness (CRF) were also investigated. Participants (65–75 years) were randomly assigned to four groups and prescribed either CE plus 35 min of rest (n = 21, 52% female); PE [performed on a cycle ergometer at moderate intensity (65–75% of individual maximal heart rate)] plus 35 min of rest (n = 27, 56% female); CE plus PE (n = 24, 46% female), or PE plus CE (n = 25, 52% female). Groups were tested for CRF using a maximal treadmill ergometer test (VO2peak); BDNF levels (collected 48 h after CRF) during baseline, after first exercise (PE or CE) and after second exercise (PE, CE or rest); and cognitive ability pre and post 12-week training. At both pre and post, pBDNF increased after CE and PE (up to 222%), and rest (∼67%), whereas sBDNF increased only after PE (up to 18%) and returned to baseline after rest. Acute but not prolonged PE increased both pBDNF and sBDNF. CE induced acute changes in pBDNF only. Baseline pBDNF was positively associated with baseline sBDNF (n = 93, r = 0.407, p < 0.001). No changes in CRF were found in any of the groups. Baseline CRF did not correlate with baseline BDNF. Even though baseline pBDNF and sBDNF were associated, patterns of changes in pBDNF and sBDNF in response to exercise were explicitly different. Further experimental scrutiny is needed to clarify the biological mechanisms of these results.