Linear and nonlinear viscoelasticity of aqueous solutions of ethyl(hydroxyethyl)cellulose (EHEC) in the presence of a surfactant (sodium dodecyl sulfate (SDS) or cetyltrimethylammonium bromide (CTAB)) have been examined over an extended polymer concentration regime at different surfactant-to-polymer ratios (r). By tuning the value of r and the polymer concentration, the strength of the polymer-surfactant associations can be modulated. At moderate levels of surfactant addition, the viscosity enhancement is much more pronounced for the EHEC-SDS system than for the EHEC-CTAB system. The frequency dependencies of the dynamic moduli cannot in general be described by a simple Maxwell model, but the rheological behavior is more complex with a distribution of relaxation modes. For EHEC solutions without surfactant, the polymer concentration dependence of the zero-shear viscosity eta (0) can above the entanglement concentration be described by a power law (eta (0) similar to C-x, with x = 4.1). By addition of CTAB, the main effect is that the power-law regime is extended toward lower polymer concentrations. In the presence of SDS, a more complex picture appears, with three power law regimes for the polymer-surfactant composition giving rise to the strongest association structures. These results can partially be interpreted in the framework of a model by Rubinstein and Semenov (Macromolecules 2001, 34,1058) for entangled associating polymer solutions. Significant shear-thinning effects and deviations from the Cox-Merz rule are observed for systems exhibiting pronounced polymer-surfactant interactions.