Studies of the phase diagram and linear viscoelasticity of aqueous solutions of hydrophobically modified hydroxyethyl cellulose (HMHEC), a thickener used in water-based paints, and SDS reveal that SDS-HMHEC mixed micelles are formed that increase the number of hydrophobic junctions and enhance interpolymer association up to an [SDS]/[HMHEC] ratio. This fact produces a strong increase of viscoelasticity or a phase separation, depending on the [HMHEC]. At higher ratios the excess of micelles with predominant SDS isolates hydrophobes and disrupts the micellar network. Then, viscoelastic functions decrease and HMHEC behaves as a nonassociative polymer. TTAB and Brij30 also interact with HMHEC, but in a different way. No phase separation is observed with these surfactants. TTAB forms mixed micelles and new junction points in the same way as SDS. However, this surfactant does not stabilize the micelles as SDS does, presumably due to the different interaction between the OH from the cellulose and the charged groups. Results seem to indicate that Brij30 enters into the hydrophobic aggregates of HMHEC and stabilizes them, increasing relaxation time, but it does not form new junction points, since it forms quite big micelles.