We report atomistic computer simulations of some albumin subdomains on a hydrophobic graphite surface. The simulations are carried out in an effective dielectric medium by simple energy minimization and by long molecular dynamics (MD) runs. Further energy minimizations and shorter MD runs in the explicit presence of water are also performed to assess the stability of the geometries found and to describe the change of solvation of the adsorbed subdomains. We find that the initial adsorption is accompanied by significant rearrangements of the strands in contact with the surface, otherwise preserving the secondary structure and the overall globular shape. Much larger rearrangements take place at longer times during the MD runs, eventually yielding a thin layer of amino acids covering the surface as much as possible with complete denaturation. The interaction and strain energies of the adsorbed subdomains are discussed, together with their size and overall shape changes. The proposed adsorption mechanism is fully consistent with recent experimental findings for albumin on hydrophobic surfaces.