Polyethylene oxide (PEO) based polymer electrolytes are still the state of the art for commercial lithium-metal batteries (LMBs) despite their remaining challenges such as the limited ionic conductivity at ambient temperature. Accordingly, the realization of thin electrolyte membranes and, thus, higher conductance is even more important, but this requires a sufficiently high mechanical strength. Herein, the incorporation of nanocrystalline cellulose into PEO-based electrolyte membranes is investigated with a specific focus on the electrochemical properties and the compatibility with lithium-metal and LiFePO$_4$-based electrodes. The excellent cycling stability of symmetric Li||Li cells, including the complete stripping of lithium from one electrode to the other, and Li||LiFePO$_4$ cells renders this approach very promising for eventually yielding thin high-performance electrolyte membranes for LMBs.