Encapsulation with edible films is a promising approach that may solve the disadvantages associated with the use of bioactive compounds as food additives. This is particularly relevant in the case of probiotics, since their stability in food matrices and in the gastrointestinal tract may be rather poor. Therefore, new cellulose-based edible films have been successfully developed and characterized. Sodium carboxymethyl cellulose (CMC) and hydroxyethyl cellulose (HEC) were used for the film preparation and cross-linked with citric acid (CA) under reasonably mild conditions. Model probiotic bacteria (Lactobacillus rhamnosus GG) were incorporated in the films either during the film formation and casting or after the film synthesis, via bacteria diffusion and adsorption. The later approach could efficiently entrap and preserve viable bacteria. The mechanical properties and swelling ability could be tuned by varying the HEC/CMC ratio and the amount of CA. Moreover, the surface area and total pore volume of the films considerably decreased after cross-linking. Overall, these novel films are regarded as promising inexpensive and friendly matrices for food protection and packaging applications.