Entropy-driven assembly of nematic liquid-crystal phases of cellulose nanocrystals (SCNCs) in aqueous suspensions results in the emergence of a cholesteric liquid crystalline phase (N* phase). We report that a solvated, non-adsorbing, highly branched natural polysaccharide, Gum Arabic (GA), strongly affects the assembly of the SCNCs and modifies the phase diagram: GA leads to significant crowding of the SCNC rods and induces a new liquid-liquid phase transition, where SCNC-rich and GA-rich droplets coexist. The solvated GA does not induce coagulation or gelation of the suspended SCNCs (at low concentrations of 1-3 wt% of GA). In the SCNC-rich droplets, finite-sized nematic nano-islands assemble and further evolve into cholesteric tactoids and nucleate the formation of the N* phase at significantly lower concentration (about 1.5 wt%) than in GA-free suspensions. We observe that the inter-particle distance and the chiral pitch of the N* phase are determined by the concentration of GA (for a given SCNC concentration). The resulting mesophases are characterized