Nowadays, plastic materials play an important role in almost every aspect of our daily life. However, they are not biodegradable and cause serious environmental problems. For this reason, biopolymers, such as proteins and polysaccharides, are becoming suitable alternatives. Soy protein is a potential option to reduce or even replace petroleum-based materials due to its abundance and availability. It is extracted as a by-product from the production of soy oil. Therefore, its use to manufacture added value-products can also contribute to the valorization of agro-industrial by-products. Additionally, lignin-free cellulose can be obtained from algae waste when agar is extracted from red marine seaweeds and can be used as a filler to manufacture protein-based biocomposites. Regarding manufacture methods, the conventional techniques employed for conventional plastics, such as extrusion and injection, were used in this work to process the biocomposites in order to develop competitive materials for commercial applications. The changes observed by FTIR analysis indicated that there was a good interaction between the protein and the filler; this fact was supported by the morphology of the biocomposites, which showed no agglomeration. Furthermore, protein-based biocomposites exhibited excellent barrier properties against lipids and oxygen, highlighting the potential use of these biocomposites as food packaging.