Sphingomonads are isolated at exceptionally high frequency from organic polluted environments and assumed to be more hydrophobic than other Gram-negative bacteria. However, the potential roles of cell-surface hydrophobicity (CSH) in the cell survival in polluted environment, as well as the mechanisms underlying the CSH of sphingomonads, remain unclear. Sphingobium hydrophobicum C1(T) is a highly hydrophobic sphingomonad isolated from electronic-waste contaminated sediment. In this study, we found that exposure to the typical pollutants in electronic-waste contaminated sediment, such as the heavy metal ion Pb and the organic compound deca-brominated diphenyl ether (deca-BDE), resulted in the development of even higher CSH of the hydrophobic strain C1(T); but no significant change was observed in the low CSH of its hydrophilic variant C2. The hydrophobic strain C1(T) achieved higher biomass yield in standing conditions and adsorbed more amounts of hydrophobic deca-BDE than its hydrophilic variant C2, suggesting that the high CSH potentially enhanced the adaptation of hydrophobic strain to colonize in sediment and adsorb hydrophobic nutrients. The identification of the bacterial cell-surface constituents showed that the high CSH of S. hydrophobicum was contributed greatly by outer-membrane proteins, particularly membrane transporters functioning as enhancers for nutrient uptake and stress sustainment. This study will enhance our understanding of the adaptive strategies of sphingomonads in contaminated environments. It will be of great importance to enhance the CSH of sphingomonads and utilize them in cleaning up the environment from organic pollution.