Graphene is considered to be an ideal reinforcement in metals, and its strengthening to the metal matrix is found to be the combined effect of load-sharing and the alteration of dislocation activity in the matrix. In this study, uniaxial compression tests were performed on graphene (reduced graphene oxide, RGO)-Al nanolaminated composite micro-pillars with different RGO in-plane sizes and laminate orientations. We elaborately controlled the processing parameters so that the composites with different RGO in-plane sizes shared the same RGO volume concentration and total RGO/Al interface area. It was found that the strength of RGO-Al composite pillars increased with decreasing RGO in-plane size, regardless of the laminate orientations relative to the loading direction (iso-strain or iso-stress). A clear transition in deformation mechanism existed in RGO-Al composite pillars having iso-strain configuration, from shear fracture in pillars with larger RGO in-plane size, to kink banding in pillars with smaller RGO nanosheets. These observations were interpreted by isotropic and kinematic hardening mechanisms, the superior constraining effect of smaller RGO nanosheets over dislocation transmission and motion, and the crack propagation in Al lamellae across the pillar interior. This work indicates that the mechanical behavior of graphene-reinforced metal matrix composites (MMCs) can be tailored by carefully tuning the geometry of the graphene nanosheets, without changing their type and concentration.