The surface-induced rearrangement of distant protein strands adsorbed on a hydrophobic graphite surface is investigated through atomistic molecular dynamics simulations and energy minimizations. We show that fragments both of globular proteins consisting of either beta-helices or beta-sheets and of a fibrous protein containing a triple helix do form parallel strands on this surface, irrespective of their native structure. On the other hand, a new secondary structure consisting of beta-sheets lying on the surface was never observed even after a long simulation time. The parallel ordering is characteristic of graphite being absent, for instance, on a hydrophilic poly(vinyl alcohol) surface. Our simulations indicate that this result is not related to the surface rigidity, and we suggest that it is due to a combination of the surface hydrophobicity, crystallinity, and smoothness.