A theoretical model describing the effect of grain size distribution in the metal matrix of metal-graphene composite on its yield strength. The model describes the initial stage of plastic deformation in metal-graphene composites and takes into account both dislocation mechanisms of plasticity and the process of grain boundary sliding. The yield strength of the aluminum-graphene composite was calculated depending on the average grain size of the matrix and the volume fraction of graphene. Our analysis shows that the presence of dispersion in the grain size distribution of the metal matrix decreases the yield stress so special attention should be paid to reducing this dispersion during the synthesis of the composite.