Volatile phenols have been implicated as contributors to off-odors associated with taints from bushfire smoke and microbial spoilage. Various methods for the amelioration of off-odors have been evaluated, but to date, they have not included cyclodextrin (CD) polymers. In the current study, two CD polymers were prepared from β- and γ-CD, using hexamethylene diisocyanate (HDI) as a crosslinking agent. Adsorption tests were performed with four volatile phenols (guaiacol, 4-methylguaiacol, 4-ethylguaiacol and 4-ethylphenol) at concentrations up to 1 mg/L. The removal of volatile phenols by CD polymers achieved equilibrium almost instantly, with isotherm tests suggesting an adsorption capacity of 20.7 µg of volatile phenol per gram of polymer. Langmuir and Freundlich models were subsequently used to fit the data. In batch adsorption tests, the CD polymers achieved 45 to 77% removal of volatile phenols. Polymer reusability was also evaluated and was found to be excellent. A comparison between volatile phenol adsorption by CDs vs. CD polymers, determined using a novel four-phase headspace solid-phase microextraction (HS-SPME) method for gas chromatography-mass spectrometry (GC-MS), suggests CD polymers offer several advantages for use by the wine industry.