The superior intrinsic mechanical properties of graphene have been widely studied and utilized to enhance the mechanical properties of various composite materials. However, it is still unclear how heterostructures incorporating graphene behave, and to what extent graphene influences their mechanical response. In this work, a series of graphene/Al2O3 composite films were fabricated via atomic layer deposition of Al2O3 on graphene, and their mechanical behavior was studied using an experimental-computational approach. The inclusion of monolayer chemical vapor deposited graphene between ultrathin Al2O3 films (1.5-4.5 nm thickness) was found to enhance the overall stiffness by as much as 70% compared to a pure Al2O3 film of similar thickness (∼150 GPa to ∼250 GPa). Here, for the first time, the combination of graphene and Al2O3 in vertically-stacked heterostructures results in advanced hybrid films of unprecedented mechanical stiffness that also possess qualities desirable for graphene-based transistors and flexible electronics.