Oppositely charged polyelectrolytes often form polyelectrolyte complexes (PECs) due to the association through electrostatic interactions. Obtaining PECs using natural, biocompatible polyelectrolytes is of interest in the food, pharmaceutical, and biomedical industries. In this work, PECs were prepared from two biopolymers, positively charged chitosan and negatively charged alginate. We investigate the changes in the structure and properties of PECs by adding sodium chloride (salt doping) to the system. The shear modulus of PECs can be tuned from ∼10 to 104 Pa by changing the salt concentration. The addition of salt led to a decrease in the water content of the complex phase with increasing shear modulus. However, at a very high salt concentration, the shear modulus of the complex phase decreased but did not lead to the liquid coacervate formation, typical of synthetic polyelectrolytes. This difference in phase behavior has likely been attributed to the hydrophobicity of chitosan and long semiflexible alginate and chitosan chains that restrict the conformational changes. Large amplitude oscillatory shear experiments captured nonlinear responses of PECs. The compositions of the PECs, determined as a function of salt concentration, signify the preferential partitioning of salt into the complex phase. Small-angle X-ray scattering of the salt-doped PECs indicates that the Kuhn length and radius of the alginate–chitosan associated structure qualitatively agree with the captured phase behavior and rheological data. This study provides insights into the structure–property as a function of salt concentration of natural polymer-based PECs necessary for developing functional materials from natural polyelectrolytes.