The packaging material must be safe for food, humans, and the environment, which makes the work on creating edible biodegradable packaging from polymers relevant. In this work, sustainable edible carrageenan/starch nanodispersions reinforced with nanocellulose (NC) for packaging (coating) of products were developed to improve their shelf life and preservation. The effect of the polysaccharide ratio and NC particle forms on nanodispersion properties and coating process was investigated. Various analysis methods were applied to study nanodispersions, determining particle shape, size, density, surface tension, viscosity, and contact angles onto fruits/vegetables. Nanodispersions were coated onto apples, bananas, and peppers for evaluation of their storage. The nanodispersions with 33.3/66.7 wt % carrageenan/starch with 5% NC fibrils or 10% NC crystals demonstrated the potential for applying on fruits as packaging due to decreased water loss from fruits/vegetables. They can be used prospectively by spraying on fruits/vegetables during harvesting since they consist of components actively used in the food industry.