In this study, we developed a simple and powerful method to fabricate flexible and lightweight graphene-based composites that provide high electromagnetic interference (EMI) shielding performance. Electrospun waterborne polyurethane (WPU) that featured sulfonate functional groups was used as the polymer matrix, which was light and flexible. First, graphene oxide (GO)/WPU composites were prepared through layer-by-layer (L-b-L) assembly of two oppositely charged suspensions of GO, the cationic surfactant (didodecyldimethylammonium bromide, DDAB)-adsorbed GO and intrinsic negatively charged GO, depositing on the negatively charged WPU fibers. After the L-b-L assembly cycles, the GO bilayers wrapped the WPU fiber matrix completely and revealed fine connections guided by the electrospun WPU fibers. Then, we used hydroiodic acid (HI) to obtain highly reduced GO (r-GO)/WPU composites, which exhibited substantially enhanced electrical conductivity (approximately 16.8 S/m) and, moreover, showed a high EMI-shielding effectiveness (approximately 34 dB) over the frequency range from 8.2 to 12.4 GHz.