Graphene has attracted tremendous interest in reinforcing fillers due to its unique structure and excellent physical properties. However, efficient reinforcement has been largely limited because graphene tends to agglomerate within a polymer matrix. In this study, direct reduction of graphene oxide (GO) in water in the presence of acid-treated multi-walled carbon nanotubes (t-CNTs) results in a homogeneous dispersion of reduced graphene oxide (r-GO) and t-CNT hybrids. The three dimensional r-GO/t-CNTs hybrids (abbreviated as G-CNT hybrids) possess unique properties, making them ideal reinforcing fillers for polymer nanocomposites. Poly(vinyl alcohol) (PVA) composite containing G-CNT hybrids is then prepared by a simple water casting method. Due to the synergistic interaction of the two kinds of nanofillers, the tensile strength and Young’s modulus of the resulting PVA nanocomposite filled with only 0.6 wt% G-CNT hybrids are significantly improved by about 77% and 65%, respectively. The results indicate that the nanohybrids are well dispersed throughout the PVA matrix and form strong interfacial interactions with the matrix. Besides, the presence of G-CNT hybrids slightly increases the thermal stability at 5% weight loss and remarkably improves the amount of residues of PVA nanocomposites. For comparison, we also prepare a PVA composite with the addition of only t-CNTs and find that its mechanical properties show limited enhancement owing to the decreased length-to-diameter ratio and structural defects of CNTs by acid treatment. Our work therefore provides a new way for the preparation of hybrid carbon nanomaterials with unique structure and excellent properties for fabricating high-performance polymer nanocomposites.