Formation of polyelectrolyte–surfactant complexes (PE–S) between an anionic polyelectrolyte, poly(sodium 2-sulfamate-3-carboxylate isoprene)-block-poly(ethylene oxide) (PSCI-PEO) and a cationic fluorosurfactant, N-(3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,10-heptadecafluorodecyl) pyridinium chloride (HFDPCl) was studied in alkaline aqueous solutions by static, dynamic and electrophoretic light scattering. The structure of the formed PE–S nanoparticles was investigated by SAXS, cryogenic transmission electron microscopy and atomic force microscopy. The results show that the tendency of the fluorosurfactant to form elongated threadlike micelles drives the PE–S co-assembly to a flexible core–shell cylindrical morphology with the core of the PE–S and the shell of the PEO blocks. Unlike other PE–S systems involving double hydrophilic polyelectrolytes, well-defined core–shell particles exist only in the narrow range of HFDPCl-to-PSCI unit stoichiometric ratios corresponding to zero ζ-potential of the aggregates.