Cognitive flexibility, the capacity to update behavior to meet the needs of a changing environment, is crucial to daily life and is notably compromised in advancing age. The neuromodulator Acetylcholine (ACh) is known to support cognitive flexibility in young animals and humans, and declining cholinergic function contributes to cognitive aging. We sought to gain insight on how cholinergic neuromodulation supports cognitive flexibility, how this contributes to declining cognitive flexibility seen in normal aging, and whether a body-brain manipulation could be utilized to combat such decline. We assessed cognitive flexibility by challenging subjects to overcome proactive interference (PI), the phenomenon wherein past learning impinges on new learning for similar information, using a paired associate task that can be performed with both rodents and human participants. First, we combined pharmacological manipulation of ACh with a comparison of young vs. aged Long Evans rats performing the PI resolution task to probe the interacting influence of cholinergic modulation and aging on cognitive flexibility. We demonstrated that aging and ACh inhibition have strikingly similar, non-additive effects. We then recorded cortical population activity from the frontoparietal cortices of young and aged rats resolving PI with and without ACh manipulation to determine how this cortical system, known to support cognitive flexibility, is modulated by ACh. Our results indicated that ACh-dependent beta oscillations in the posterior parietal cortex are important for cognitive flexibility. Finally, building on past research indicating that the vagus nerve, a key regulator of the parasympathetic nervous system, may drive cortical ACh activity, and that vagal activity declines with age similarly to ACh and cognitive function, we explored whether elevating vagal activity could reduce age effects on cognitive flexibility in humans. Young and older adults performed the PI resolution task paired with a breathing manipulation that boosted vagal function, which elevated older adults’ cognitive flexibility to mimic that of young adults. Our results shed light on the role of ACh in age-related declines in cognitive flexibility, the neural mechanisms underlying this, and possible routes of intervention.