M06-2X/6-31G(d) level calculations were performed to examine the interactions of two alpha-amino acids (histidine and proline) individually with two finite-sized graphene sheets (C62H20 and C186H36). The conformers and orientations of histidine and proline on the surface of graphene play an important role in determining the stabilities of complexes. The number and type of non-bonding interactions such as pi-pi, C-H center dot center dot center dot p, N-H center dot center dot center dot p and O-H center dot center dot center dot p account for the stabilization of the complexes. The binding energy in aqueous phase generally decreases compared to gas phase. HOMO-LUMO energy gap of graphene is not altered by binding of either proline or histidine.