Polysaccharide and proteins are the major constituent building blocks of biological systems and often occur as highly organized macromolecular architectures (e.g. the capsid of viruses). Both can occur in the same or in different biological physiological environment interacting in specific or non-specific ways. When isolated and purified, these macromolecules can harness self-assembled (SA) soft nanomaterials by non-covalent electrostatic complexation. Although polysaccharide-protein electrostatic SA systems of this type have been studied for more than two decades, the possibility to design materials with enhanced biological function and improved technological advantages over those based on synthetic or inorganic components, has only started to be recognized and is yet to be fully realized. In this review we address two main type of SA polysaccharide-protein systems, namely, those based on chitosan-protein and those based on polyanionic polysaccharide (pectin, hyaluronic acid or alginate) - protein ones. The physical properties of chitosan- and polyanion-based SA nanocomplexes with oppositely charged proteins depend on the composition and conditions as reviewed here with reference to some specific systems.