Formation of polyelectrolyte-surfactant (PE-S) complexes of poly(ethylene oxide)-block-poly(methacrylic acid) (PEO705-PMAA(476)) and N-dodecylpyridinium chloride (DPCl) in aqueous solution was studied by static and dynamic light scattering (SLS, DLS), small-angle neutron scattering (SANS), small-angle X-ray scattering (SAXS), and cryogenic transmission electron microscopy (cryo-TEM). While it was found previously [Macromolecules 1997, 30, 3519] by microcalorimetric titration that in a similar system (PEO176-PMAA(186)) crystallization of aliphatic tails of N-dodecylpyridinium bromide did not occur, in our system it was evidenced by SAXS that upon addition of DPCl to fully ionized PEO705-PMAA(476) the ordered arrangement of the surfactant occurs in a certain range of PEO705-PMAA(476) concentrations and surfactant-to-polyelectrolyte charge molar ratio (Z). Our data suggest a four-step process in the behavior of the PEO705-PMAA(476)/DPCl system: (I) coexistence of loose aggregates of electrostatically bound surfactants to PMAA block with free and almost unperturbed copolymer coils at Z << 1, (ii) formation of aggregates containing ill-defined cores formed by DPCl micelles attached to coiled PMAA chains (beads-on-a-string nanoparticles) in the range around Z = 0.5, (iii) formation of compact core-shell nanoparticles with a core formed by densely packed ordered (crystalline) DPCl micelles and PEO shell starting slightly before charge equimolarity (Z = 1), and (iv) the region of coexistence of the core shell nanoparticles with free DPCl micelles in excess above equimolarity (Z >> 1). In the region around Z = 0.5, the nanoparticles with nonordered cores coexist in a mixture either with a fraction free chains and large swollen nanoparticles decorated by surfactant micelles (at lower Z) or with the core shell nanoparticles (at higher Z). PE-S complexes were characterized in detail in terms of molar mass, size, shape, and internal structure.