We report a small-angle neutron scattering (SANS) study of semidilute aqueous solutions of sodium carboxymethyl cellulose (NaCMC), in the presence of mono- (Na+) and divalent salts (Mg2+, Ca2+, Zn2+, and Ba2+). A degree of substitution of 1.3 is selected to ensure that, in salt-free solution, the polymer is molecularly dissolved. We find that Na+ and Mg2+ salt addition yields H-type phase behavior, while Ca2+, Zn2+, and Ba2+ instead yield a mixed H/L-type phase behavior dependent on the NaCMC concentration (cp), in the decreasing order of the salt concentration required to induce turbidity (at a fixed cp). Charge screening by addition of NaCl induces the disappearance of the characteristic polyelectrolyte correlation peak and eventually yields scattering profiles with a q–1 dependence over nearly 3 decades in the wavenumber q. By fitting a descriptive model to data with excess Na+, we obtain a correlation length ξ′ = 1030 cp–0.72 Å with cp in g L–1. Addition of Mg2+, which does not interact specifically with NaCMC carboxylate groups, yields an analogous screening behavior to that of Na+, albeit at lower salt concentrations, in line with its higher ionic strength. At low salt concentration, addition of specifically interacting Ca2+, Zn2+, and Ba2+ yields a comparatively greater screening of the polyelectrolyte correlation peak, and at concentrations above the phase boundary, results in excess scattering at low-q, compatible with the formation of 20–40 nm clusters. This behavior is interpreted as due to the reduction in charge density along the chain, promoting interchain association and multichain domain formation resulting in visible turbidity. Overall, drawing analogies with NaCMC at a lower degree of substitution, where hydrophobic association takes place, our findings provide a framework to describe the solution structure and phase behavior of NaCMC in salt-free and salt solutions.