Bacterial adhesion to surfaces is a crucial step in initial biofilm formation. In a combined experimental and computational approach, we studied the adhesion of the pathogenic bacterium Staphylococcus aureus to hydrophilic and hydrophobic surfaces. We used atomic force microscopy-based single-cell force spectroscopy and Monte Carlo simulations to investigate the similarities and differences of adhesion to hydrophilic and hydrophobic surfaces. Our results reveal that binding to both types of surfaces is mediated by thermally fluctuating cell wall macromolecules that behave differently on each type of substrate: on hydrophobic surfaces, many macromolecules are involved in adhesion, yet only weakly tethered, leading to high variance between individual bacteria, but low variance between repetitions with the same bacterium. On hydrophilic surfaces, however, only few macromolecules tether strongly to the surface. Since during every repetition with the same bacterium different macromolecules bind, we observe a comparable variance between repetitions and different bacteria. We expect these findings to be of importance for the understanding of the adhesion behaviour of many bacterial species as well as other microorganisms and even nanoparticles with soft, macromolecular coatings, used e.g. for biological diagnostics.