The interaction between hydrophobically modified hydroxyethyl cellulose (hmHEC), containing approximately 1 wt% side-alkyl chains of $C_{16}$, and an anionic sodium dodecyl sulphate (SDS) surfactant was investigated. For a semi-dilute solution of 0.5 wt% hmHEC, the previously observed behaviour of a maximum in solution viscosity at intermediate SDS concentrations, followed by a drop at higher SDS concentrations, until above the cmc of surfactant when the solution resembles that of the unsubstituted polymer, was confirmed. Additionally, a two-phase region containing a hydrogel phase and a water-like supernatant was found at low SDS concentrations up to 0.2 wt%, a concentration which is akin to the critical association concentration, cac, of SDS in the presence of hmHEC. Above this concentration, SDS molecules bind strongly to form mixed micellar aggregates with the polymer alkyl side-chains, thus strengthening the network junctions, resulting in the observed increase in viscosity and elastic modulus of the solution. The shear behaviour of this polymer-surfactant complex during steady and step stress experiments was examined In great detail. Between SDS concentrations of 0.2 and 0.25 wt%, the shear viscosity of the hmHEC-polymer complex network undergoes shear-induced thickening, followed by a two-stage shear-induced fracture or break-up of the network. The thickening is thought to be due to structural rearrangement, causing the network of flexible polymers to expand, enabling some polymer hydrophobic groups to be converted from intra- to inter-chain associations. At higher applied stress, a partial local break-up of the network occurs, while at even higher stress, above the critical or network yield stress, a complete fracture of the network into small microgel-like units, Is believed to occur. This second network rupture is progressive with time of shear and no steady state in viscosity was observed even after 300 s. The structure which was reformed after the cessation of shear is found to be significantly different from the original state.