Association behavior of the biocompatible amphiphilic cationic gradient polyelectrolyte poly[(2-methyl-2-oxazoline)-grad-(2-phenyl-2-oxazoline)-mod-(ethylene imine)] (HPPhMeOx) prepared by partial hydrolysis of the gradient copolymer poly[(2-methyl-2-oxazoline)-grad-(2-phenyl-2-oxazoline)] and the interaction of HPPhMeOx with the anionic surfactant sodium dodecyl sulfate (SDS) in aqueous solutions were investigated by scattering techniques (SANS, DLS) and by atomic force microscopy. SANS measurements revealed that large particles with the hydrodynamic radius of ca. 500 nm observed in HPPhMeOx aqueous solutions by DLS are formed by a network of physically crosslinked compact hydrophobic domains with the mean radius of ca. 10 nm. Upon addition of sodium dodecyl sulfate (SDS), the size of the domains increases at low amounts of the added SDS due to hydrophobic interaction of the single surfactant ions with the aggregates. Further addition of SDS leads to the formation of the co-assembled polyelectrolyte–surfactant complex manifested in SANS by the presence of the correlation peak from the densely packed SDS micelles as well as by partial disruption of the domains.