Associative polymers in combination with cyclodextrin (CD) provide a potent tool to manipulate the solution rheology of aqueous solutions. In this study, we discuss the viability and scope of employing surfactants in such systems to facilitate a more versatile and effective tailoring of rheological properties. The addition of either a- or b- CD to a comb-like hydrophobically-modified associative polymer (HASE) solution results in a dramatic decrease in viscosity and viscoelastic properties of the due to the encapsulation of polymer hydrophobes by CDs. Subsequent addition of nonionic surfactants to such systems promotes a competition between CDs and surfactant molecules to complex with polymer hydrophobes thereby altering the hydrophobic interactions. Three types of behavior is observed depending on the type of CD (a versus b) as well as the hydrophilic-lipophilic balance (HLB) of surfactant used: no change in rheology, a transition to a gel, or a maximum in viscosity and dynamic moduli. These reuslts are discussed based on the varying affinities of a- and b- CDs to complex with NP surfactants, reflected in the UV-vis spectroscopy and cloud point measurements, and the presence of different micellar structures in solution as dictated by surfactant HLB. These findings are of particular importance as they imply that a judicious selection of surfactant based on its HLB can offer an effective route to achieve a wide array of desired rheological properties in aqueous systems of associative polymers containing different CDs.