With the widespread use of electronic communication devices, ultra-thin, flexible, and high-performance electromagnetic interference (EMI) shielding materials are widely used to prevent radiation pollution. Moreover, graphene-reinforced polymer-based nanocomposites have received increasing attention in the field of EMI shielding because of their excellent electrical properties. In this work, ultrathin and flexible nickel/reduced graphene oxide/cellulose nanofiber (Ni/RGO/CNFs) composite paper was fabricated using a step-by-step vacuum-assisted filtration method. The prepared composite paper with Ni/RGO to CNF ratio of 3:1 and a thickness of 105 µm attained the electrical conductivity of 1664 S/m and 22.6 dB of excellent electromagnetic shielding effectiveness (SE). In addition, the composite paper (2:1) exhibited great mechanical properties, leading to a high tensile strength of 78.4 MPa, 10.3% fracture strain, and no obvious fractures or cracks when the composite paper was folded. Therefore, the Ni/RGO/CNFs composite paper prepared in this study is an effective lightweight shielding material, especially in flexible electronics and wearable devices.