A series of novel polysaccharide-based biocomposites was obtained by impregnation of bacterial cellulose produced by Komagataeibacter rhaeticus (BC) with the solutions of negatively charged polysaccharides—hyaluronan (HA), sodium alginate (ALG), or κ-carrageenan (CAR)—and subsequently with positively charged chitosan (CS). The penetration of the polysaccharide solutions into the BC network and their interaction to form a polyelectrolyte complex changed the architecture of the BC network. The structure, morphology, and properties of the biocomposites depended on the type of impregnated anionic polysaccharides, and those polysaccharides in turn determined the nature of the interaction with CS. The porosity and swelling of the composites increased in the order: BC–ALG–CS > BC–HA–CS > BC–CAR–CS. The composites show higher biocompatibility with mesenchymal stem cells than the original BC sample, with the BC–ALG–CS composite showing the best characteristics.