We use Langevin molecular dynamics simulations to study the complexation of a linear polyelectrolyte (LPE) chain with an oppositely charged soft nanoparticle, modeled by a spherical polyelectrolyte brush (SPB). By changing core radius of the SPB and length of polyelectrolyte (GPE) chains grafted at it, a structural transition from a charged, LPE-covered sphere via a softer nanobrush toward a star-like polyelectrolyte is identified. As a result, the LPE chain develops various wrapping conformations around the SPB. Our systematic analysis reveals all relevant conformational binding modes for the polyelectrolyte-nanoparticle complex. (C) 2013 Elsevier B.V. All rights reserved.