A moldable material from a natural cationic polyelectrolyte, ε-poly-l-lysine (ε-PL), was prepared by mixing with two lignosulfonates a reagent for research (L-SO3Na) and a commercially available purified lignosulfonate (Pearllex NP). The obtained ε-PL/lignosulfonate complexes demonstrated the ability to be tuned from a rigid form, such as polystyrene or poly(methyl methacrylate), to a soft elastomer form such as silicone by varying the lignosulfonate species and composition. The maximum toughness of the complex (8.4 MJ/m3) was superior to that of ε-PL or lignosulfonate-derived polyelectrolyte complexes. In addition, the ε-PL/lignosulfonate complex showed self-healing properties due to the many reversible ionic bonds in the complex. The preparation process for the novel complex was simple, involving the mixing and drying of an aqueous solution of the polyelectrolyte without any extra reagents (organic solvents, condensation reagents, and cross-linker). Thus, given these many advantages and the excellent biodegradability of the components, the ε-PL/lignosulfonate complex is expected to be useful as a sustainable structural material.