Polyelectrolyte complexes (PECs) self-assembled from bottle-brush polyelectrolytes, having a cationic main chain and uncharged side chains, and linear anionic sodium polystyrenesulfonate (NaPSS) have been investigated with emphasis on (i) the charge density and side chain density of the bottle-brush polyelectrolyte, (ii) the molecular weight of NaPSS, and (iii) the charge stoichiometry of the mixture. Light scattering and electrophoretic mobility data demonstrate that small molecular complexes are formed when the PEO 45 side chain density is sufficiently high to provide steric stabilization and prevent PEC aggregation. The adsorption of PECs on negatively charged silicon oxynitride was investigated using dual polarization interferometry, and the time evolution of the adsorbed amount and thickness was determined. Cationic, uncharged, and negatively charged complexes all adsorb to negatively charged silicon oxynitride, and maximum adsorption is achieved for positively charged complexes containing small amounts of PSS. The adsorbed amount and the kinetics of adsorption are reduced with increasing PSS content, and for any given stoichiometry with increasing PSS molecular weight. These findings are discussed in terms of the PEC structure and the ability of anionic polyelectrolytes to leave the PECs during adsorption.