Associative polymers, such as hydrophobic ethoxylated urethane (HEUR), interact with various cyclodextrins (CDs) to form inclusion complexes in aqueous solution. The rheological behavior of HEUR/CD inclusion complex solutions can be manipulated by the introduction of an anionic surfactant, such as sodium dodecyl sulfate (SDS), and such behavior is dependent on the characteristics and types of CD. The introduction of SDS partially restores the viscoelastic behavior of the HEUR/methylated beta-CD (m-beta CD) system, but it completely recovers the viscoelastic behavior of the HEUR/alpha-CD system. Such difference is attributed to the different binding affinity of SDS and CDs. Temperature dependence of the viscoelastic behavior revealed that the activation energy and plateau modulus for HEUR/alpha-CD/SDS system were higher than those of the HEUR/m-beta CD/SDS system. In excess amounts of SDS, the interaction between SDS and HEUR/CD inclusion complexes was similar to that of SDS and HEUR. Isothermal titration calorimetric study provided physical insights on the binding mechanism responsible for the recovery of the viscoelastic properties of HEUR/CD/SDS ternary systems.