Polyelectrolyte complexes (PECs) are polymeric structures formed by the self-assembly of oppositely charged polymers. Novel biomaterials based on PECs are currently under investigation as drug delivery systems, among other applications. This strategy leverages the ability of PECs to entrap drugs under mild conditions and control their release. In this study, we combined a novel and sustainably produced hemicellulose-rich lignosulphonate polymer (EH, negatively charged) with polyethyleneimine (PEI) or chitosan (CH, positively charged) and agar for the development of drug-releasing PECs. A preliminary screening demonstrated the effect of several parameters (polyelectrolyte ratio, temperature, and type of polycation) on PECs formation. From this, selected formulations were further characterized in terms of thermal properties, surface morphology at the microscale, stability, and ability to load and release methylene blue (MB) as a model drug. EH/PEI complexes had a more pronounced gel-like behaviour compared to the EH/CH complexes. Differential scanning calorimetry (DSC) results supported the establishment of polymeric interactions during complexation. Overall, PECs’ stability was positively affected by low pH, ratios close to 1:1, and the addition of agar. PECs with higher EH content showed a higher MB loading, likely promoted by stronger electrostatic interactions. The EH/CH formulation enriched with agar showed the best sustained release profile of MB during the first 30 h in a pH-dependent environment simulating the gastrointestinal tract. Overall, we defined the conditions to formulate novel PECs based on a sustainable hemicellulose-rich lignosulphonate for potential applications in drug delivery, which promotes the valuable synergy between sustainability and the biomedical field. Graphical abstract: (Figure presented.)