Using non-equilibrium molecular dynamic simulations, we investigate the effect of adsorbates on nano-scopic friction. We find that the interplay between different channels of energy dissipation at the frictional interface may lead to non-monotonic dependence of the friction force on the adsorbate surface coverage and to strongly nonlinear variation of friction with normal load (non-Amontons' behavior). Our simulations suggest that the key parameter controlling the variation of friction force with the normal load, surface coverage and temperature is the time-averaged number of adsorbates confined between the tip and the substrate. Three different regimes of temperature dependence of friction in the presence of adsorbates are predicted. Our findings point on new ways to control friction on contaminated surfaces.