Exposure to intermittent hypoxia (IH), such as occurs in sleep-disordered breathing (SDB), is associated with cognitive impairment, neurodegeneration, oxidative stress, and inflammatory responses within rodent brain regions such as the basal forebrain. In this region, damage to cholinergic neurons correlates with working memory deficits in a number of neurodegenerative disorders, suggesting that degeneration of cholinergic systems may also contribute to the working memory impairments observed after IH exposures. We therefore examined basal forebrain choline acetyltransferase (CHAT) immunohistochemistry, nicotinic receptor binding in the prefrontal cortex (PFC), and working memory, in male rats tested on a delayed matching to place (DMP) task in the water maze following exposure to either room air (RA) or intermittent hypoxia (IH; alternating 90 s epochs of 21% and 10% O2 during sleep). IH-treated animals displayed impaired working memory with respect to controls, along with significant reductions in CHAT-stained neurons in the medial septal nucleus, in both the vertical and horizontal limbs of the diagonal band, and the substantia inominata after 14 days of IH exposure. In addition, increases in nicotinic binding and receptor affinity in the PFC were observed after 14 days of IH exposure. Thus, a loss of cholinergic neuronal phenotype in the basal forebrain may contribute to the cognitive impairments associated with CIH exposure. However, compensatory mechanisms may also be activated in other brain regions, and may provide potential therapeutic targets for the cognitive impairments associated with SDB.