Cellulose microfibrils (CMF) are a unique class of shape anisotropic bio-nanomaterials, already finding many applications in diverse fields owing to their advantageous material properties and abundant availability. The rich non-linear mechanical behaviour of CMF networks has been under-studied due to the complex nature of this system, being influenced by many factors such as strong inter-fibril interactions, a heterogeneous microstructure, and process conditions. In this work, we systematically explore the non-linear rheological behaviour of these networks using a CMF model system with controlled process conditions and fibril interactions. The microfibrils were dispersed in dimethyl sulfoxide to minimise the attractive van der Waals interactions and thereby also the network heterogeneity. We show that the networks exhibit a transition with increasing shear stress from a predominantly elastic to a plastic deformation where they undergo softening. We find that the network stiffness and plasticity are dependent on the loading rate. Finally, we observed that the networks regain their original viscoelastic moduli on cessation of shear. These findings form a basis towards understanding and ultimately modelling the mechanics of CMF networks, which is a prerequisite for the rational design of novel bio-based materials.