Abstract—Theoretical models are proposed that describe the initial stage of plastic deformation in metal–graphene composites with a homogeneous ultrafine-grained metal matrix, as well as with a bimodal grain size distribution. The models take into account both dislocation mechanisms of plasticity and the processes of structural transformations of grain boundaries associated with grain-boundary sliding. As a result of the calculations, the dependences of the yield strength on the grain size of the matrix and the volume fraction of graphene were obtained. Models allow one to find the optimal graphene content to achieve maximum material strength.