There is much evidence that dopamine is vital for cognitive functioning in aging. Here we tested the hypothesis that aerobic exercise and fitness influence dopaminergic neurotransmission in the striatum, and in turn performance on offline working-memory updating tasks. Dopaminergic neurotransmission was measured by positron emission tomography (PET) and the non-displacable binding potential (BPND) of [11C]raclopride, i.e. dopamine (DA) D2-receptor (D2R) availability. Fifty-four sedentary older adults underwent a six-months exercise intervention, performing either aerobic exercise or stretching, toning, and resistance active control training. At baseline, higher aerobic fitness levels (VO2peak) were associated with higher BPND in the striatum, providing evidence of a link between an objective measure of aerobic fitness and D2R in older adults. BPND decreased substantially over the intervention in both groups but the intervention effects were non-selective with respect to exercise group. The decrease was several times larger than any previously estimated annual decline in D2R, potentially due to increased endogenous DA. Working-memory was unrelated to D2R both at baseline and following the intervention. To conclude, we provide partial evidence for a link between physical exercise and DA. Utilizing a PET protocol able to disentangle both D2R and DA levels could shed further light on whether, and how, aerobic exercise impacts the dopaminergic system in older adults.