Graphene oxide (GO) with extraordinary chemical, thermal and mechanical properties offers possibilities in a variety of applications. Many materials have been fabricated through physical blending of GO with other materials, while, the chemical functionalization of GO has generally been considered challenging. Here, we report the preparation of a novel GO-functionalized fibrous material in which individual compliant GO sheets are cross-linked by PAA chains in a near-vertical fashion. This new fibrous material outperforms many other common fibers in stiffness and strength. Combined with straightforward manufacturing methods, the fibers should find applications in a wide range of areas.