The binding of an anionic polyelectrolyte, poly(sodium 4-styrenesulfonate) (PSSS), to mixed cationic/zwitterionic surfactant micelles is observed via deuterium NMR spectroscopy. The deuteron labels are located in the polar headgroup of the zwitterionic surfactant hexadecylphosphocholine (HDPC-gamma-d6). When mixed with cationic cetyltrimethylammonium bromide (CTAB), HDPC-gamma-d6 yields a narrow deuterium NMR resonance line, the intensity of which decreases, and subsequently increases again, as a function of the concentration of added PSSS, in a manner correlating with the precipitation and resolubilization of the colloidal dispersion by PSSS. Either reducing the micellar surface charge density or increasing the ionic strength diminishes this effect of PSSS. The deuterium NMR spectrum of HDPC-gamma-d6 within the precipitated complexes consists of a broad Pake doublet characteristic of anisotropic motional averaging, indicating that a micellar structure is likely retained by the surfactants even in the aggregated state.