We present a novel approach to the fabrication of advanced polymeric nanocomposites from poly(vinyl alcohol) (PVA) by incorporation of PVA-grafted graphene oxide. In this work, we have synthesized PVA-grafted graphene oxide (PVA-g-GO) for the strong interfacial adhesion of graphene oxide (GO) to the PVA matrix. It was found that the mechanical properties of PVA were greatly improved by incorporating PVA-g-GO. For example, the tensile strength and Young’s modulus of the PVA nanocomposite films containing 1 wt % net GO in the PVA-g-GO significantly increased by 88 and 150%, respectively, as compared to unfilled PVA. The elongation at break was also increased by 22%, whereas the GO/PVA nanocomposite containing 1 wt % pristine GO was decreased by 15%. Therefore, the presence of the PVA-g-GO in the PVA matrix could make the PVA not only stronger but also tougher. The strong interfacial adhesion between PVA-g-GO and the PVA matrix was attributed to the good compatibility between PVA-g-GO and the matrix PVA as well as the hydrogen-bonding between them.