Thermoelectrochemical cells (TECs) are a promising and cost-effective approach to harvesting waste thermal energy. For the widespread uptake of this new technology and the development of flexible, leak-free devices, solidification of the redox electrolyte is key. Thus, here we report the first quasi-solid-state electrolyte incorporating the ferri/ferrocyanide redox couple within a cellulose matrix. The electrolyte with 5 wt % cellulose achieved an optimum balance of mechanical properties, Seebeck coefficients, and diffusion coefficients and supported power outputs comparable to those of the liquid electrolyte systems.