We develop a model for the adsorption of random heteropolymers onto solid surfaces from solutions that have a finite concentration of polymer. Previous studies that properly average over the quenched sequence distribution have been concerned with isolated chains near surfaces. Our self-consistent-field theory predicts a transition from situations where the surface segment density is enhanced compared with bulk solution concentration to one wherein the surface segment density is depleted. For a specific chemical identity of the random heteropolymer segments and the surface, this adsorption-depletion transition occurs above a threshold value of the strength of the sequence fluctuations. This intriguing finding can be tested directly via neutron scattering experiments (in the reflection mode), and offers opportunities for manipulating interfacial properties. The variation of the excess surface density of segments with polymer concentration in solution near the adsorption-depletion transition is also elucidated.