The formation of a complex between an anionic spherical polyelectrolyte brush (SPB) and the cationic surfactant cetyltrimethylammonium bromide (CTAB) is investigated. The SPB consists of long chains of the strong polyelectrolyte poly(styrene sulfonate) (PSS), which are bound chemically to a solid poly(styrene) core of 56 nm in radius. The SPB are dispersed in water, and the ionic strength is adjusted by addition of NaBr. The resulting complexes are investigated in dilute solution by dynamic light scattering, by electrophoretic light scattering, and by cryogenic transmission electron microscopy (cryo-TEM). The formation of the complex between the SPB and the surfactant can be monitored by a strong shrinking of the surface layer when adding CTAB to dilute suspensions (0.01 wt %) and by a decrease of the effective charge of the complexes. Complex formation starts at CTAB concentrations lower than the critical micelle concentration of this surfactant. If the ratio r of the charges on the SPB to the charge of the added surfactant is exceeding unity, the particles start to flocculate. Cryo-TEM images of the complexes at r = 0.6 measured in salt-free solution show that the surface layer composed of the PSS chains and the adsorbed CTAB molecules is partially collapsed: A part of the chains form a dense surface layer while another part of the chains or aggregates thereof are still sticking out. This can be deduced from the cryo-TEM micrographs as well as from the hydrodynamic radius, which is still of appreciable magnitude. The 1:1 complex (r = 1.0) exhibits a fully collapsed layer formed by the PSS chains and CTAB. If the complex is formed in the presence of 0.05 M NaBr, r = 0.6 leads to globular structures directly attached to the surface of the core particles. All structures seen in the cryo-TEM images can be explained by a collapse transition of the surface layer brought about by the hydrophobic attraction between the polyelectrolyte chains that became partially hydrophobic through adsorption of CTAB.