Polyelectrolyte/surfactant complexes formed between well-defined linear flexible polyelectrolytes, namely, quaternized poly[3,5-bis(dimethylaminomethylene)hydroxystyrene] (Q-N-PHOS), bearing two cationic sites on each repeating unit, and two different anionic surfactants, namely, sodium dodecyl sulfate (SDS) with one hydrocarbon tail and sodium bis(2-ethylhexyl) sulfosuccinate (AOT) with two hydrocarbon chains, are studied by means of fluorescence spectroscopy, electrophoretic, dynamic and static light scattering, and atomic force microscopy. Depending on the surfactant state in initial solutions (i.e., below or above nominal critical micelle concentration, cmc) and final (-/+) charge ratio, self-assembly in nanoparticles of variable size, stability, and effective charge is possible. Spherical, rather polydispserse complexes are formed in all cases. Critical aggregation concentrations (cac) depend on the surfactant type, while hydrophobicity of the main polyelectrolyte chain plays a role in colloidal stability of the complex nanoparticles.