This study addresses the synthesis and mechanical behavior of graphene-metal composites comprising palladium (Pd) nanoribbons wrapped with graphene. Coating Pd nanoribbons with graphene by chemical vapor deposition (CVD) considerably increases their elastic modulus. These measurements are made by suspended microbridge indentation. A refined indentation measurement approach carefully takes into consideration the uncertainty resulting from the non-ideal bridge geometry. The measured composite moduli depend on the ribbon thickness in the range of 36–250 nm, with the maximum modulus of 147 GPa measured for 36 nm thick nanoribbons, representing an increase of 41.6% over uncoated Pd nanoribbons. The results clearly demonstrate that graphene, owing to its high modulus and strong interaction with Pd, can effectively reinforce Pd nanoribbons up to thickness of 250 nm, which corresponds to a volume fraction of 0.54%. We study the modulus scaling by deriving a mathematical rule of mixture model considering 3D ‘bulk’ metal nanoribbons reinforced by the 2D graphene ‘surface’. This modeling approach is inspired by the framework of surface modulus, which is typically employed to explain the deviations in the moduli of nanowires and nanoribbons observed in the sub-10 nm regime. Here, the nanoribbons are much thicker, yet graphene’s extremely high modulus leads to the observed increase in the measured composite moduli. Further, in these calculations, we consider the critical role of the nonlinear modulus component of graphene -its quadratic dependence on strain- which results from the lattice mismatch-induced interfacial strains between graphene and Pd. Graphene-Pd composite nanoribbons and thin films can be very useful for a wide range of application ranging from strain-engineered catalysis to damage tolerant flexible electronic devices. Beyond nanoribbons, the proposed 3D/2D rule of mixture model may be used to explain the modulus scaling in 3D/2D heterostructures and in bulk graphene-metal nanocomposites made by powder mixing routes.