Electromagnetic interference pollution has raised urgent demand for the development of electromagnetic interference shielding materials. Transition metal carbides (MXenes) with excellent conductivity have shown great potential in electromagnetic interference (EMI) shielding materials, while the poor mechanical strength, flexibility, and structural stability greatly limit their further applications. Here, cellulose nanofibers and sodium alginate are incorporated with MXene nanosheets as flexible matrices to construct strong and flexible mussel-like layered MXene/Cellulose nanofiber/Sodium Alginate composite films, and nickel ions are further introduced to induce metal coordination crosslinking of alginate units. Benefited from the dual-crosslinked network structure of hydrogen bonding and metal coordination, the tensile strength, Young’s modulus, and toughness of the MXene/cellulose nanofiber/nickel alginate composite film are significantly increased. After subsequent reduction by ascorbic acid, excess nickel ions are reduced to nickel nanoparticles and uniformly dispersed within the highly conductive composite film, which further improved its hysteresis loss effect toward the incident electromagnetic waves. Consequently, the MXene/cellulose nanofiber/nickel alginate-Ni composite film presents a considerably enhanced electromagnetic interference shielding effectiveness (47.17 dB) at a very low thickness of 29 μm. This study proposes a feasible dual-crosslinking and subsequent reduction strategy to synergistically enhance the mechanical properties and electromagnetic interference shielding performance of MXene-based composite materials.