The present study describes the synthesis and characterization of a series of four composite electrolytes for lithium ion battery applications. The two-phase electrolytes are composed of a soft, ionic conductive poly(ethylene glycol) (PEG) matrix having stiff nanofibrillated cellulose (CNF) paper as reinforcement to provide mechanical integrity. The reinforcing CNF is modified in order to create covalent bonds between the phases which is particularly beneficial when swelling the composite with a liquid electrolyte to enhance the ionic conductivity. After swelling the composite polymer electrolyte, forming a gelled structure, values of ionic conductivity at 5 × 10-5 S cm-1 and an elastic modulus around 400 MPa at 25 °C are obtained.