Flexible and light weight electromagnetic interference (EMI) shielding materials with high electromagnetic shielding efficiency (SE) and excellent mechanical strength are highly demanded for wearable and portable electronics. In this work, for the first time, a freestanding and flexible cellulose nanofibril (CNF)/PEDOT:PSS/MXene (Ti3C2Tx) nanocomposite film with a ternary heterostructure was manufactured using a vacuum-assisted filtration process. The results show that compared with pure MXene films, the tensile strength of the optimized nanocomposite film increases from 8.88 MPa to 59.99 MPa, and the corresponding fracture strain increases from 0.87% to 4.60%. Intriguingly, the optimized nanocomposite film exhibited an impressive conductivity of 1903.2 S cm-1, which is among the highest values reported for MXene and cellulose-based nanocomposites. Owing to the superior conductivity and unique heterostructure, the nanocomposite film exhibits a high EMI SE value of 76.99 dB at a thickness of only 58.0 μm. Taking into account the robust mechanical properties and remarkable EMI shielding performance, the CNF/PEDOT:PSS/MXene nanocomposite film could be a prospective EMI shielding material for a variety of high-end applications.