Self-assemblies of the divalent surfactant dodecyl-1,3-propylenepentamethylbis(ammonium chloride) (DoPPDAC) and the monovalent dodecyltrimethylammonium bromide (DoTAB) were investigated in dilute solutions of anionic polyelectrolytes. Pyrene probing showed that the critical aggregation concentration (cac) was about the same for the two surfactants in solutions of a given polyion. The polyions could be arranged in order of increasing cac: dextran sulfate < polyvinyl sulfate < polyacrylate < poly(styrenesulfonate) < carboxymethyl cellulose. The surfactant aggregation number (N) for DoPPDAC, obtained from time-resolved fluorescence quenching, was 2-3 times smaller than that for DoTAB in the presence of all polyions. With poly(styrenesulfonate) taken out of consideration, it was found that a large N correlated with a low cac, and vice versa. For both surfactants, pyrene lifetime measurements indicated an insignificant binding of negatively charged quenchers to the micelles, showing that the micelle charges were neutralized mainly by the polyions. The presence of polyion reduced the quenching by oxygen dissolved in the water. The effect was larger for DoPPDAC than for DoTAB, suggesting that the micelles of the former are surrounded by a more dense layer of polyion.