Mixtures of polyelectrolytes and oppositely charged surfactants show very rich phase behavior that is influenced by surfactant-ion and polyion properties and by water content. A general feature is associative phase separation as a result of strong electrostatic interactions, whereas the effect of eventual more specific interactions (e.g., hydrophobic) has not been thoroughly investigated. In this paper, we report a detailed study on phase behavior and structures in poly(styrenesulfonate anion) (PSS-)-cetyltrimethylammonium cation (CTA(+))-water mixtures that are characterized by a hydrophobic interaction between the styrene groups of PSS- and the micelle interior. Structures of various phases were determined by small-angle X-ray scattering, and results indicated the presence of a disordered micellar and an ordered hexagonal phase; no cubic phase was found. The general conclusion is that the highlighted hydrophobic interaction promotes dissolution of CTAPSS when the polyion salt is added and provides further stabilization of the dense phase when the surfactant salt is added.