The interactions between a globular protein, hen egg white lysozyme (HEWL), and star-like block polyelectrolyte micelles formed by the self-assembly of a poly(tertbutylstyrene)-b-poly(sodium(sulfamate-carboxylate)isoprene) (PtBS-SCPI) amphiphilic diblock copolymer were studied in aqueous solutions. Due to the opposite charges present in HEWL (positive charges) and on the SCPI polyelectrolyte coronas of the block copolymer micelles (negative charges), nanostructured hierarchical complexes are formed at neutral pH and low ionic strength. Structure and properties of the complexes were investigated by means of dynamic, static and electrophoretic light scattering, as well as atomic force microscopy. The solution behaviour, structure and effective charge of the formed nanoscale complexes proved to be dependent on the ratio of the two components. Presumably block polyelectrolyte micelles with a PtBS core and a SCPI corona decorated with HEWL molecules are initially formed. Moreover, the degree of charge neutralization caused by complexation determines the conformation and solubility of the complexes. Complexation of the macromolecular components at higher solution ionic strengths led to complexes of lower mass and nearly constant size. Such behavior may be correlated to the polyelectrolyte nature of the components. The structural investigation of the complexed protein by fluorescence and infrared spectroscopy revealed no signs of HEWL denaturation upon complexation.