Traditional food packaging materials maintain food quality and safety during storage, but they cause significant environmental pollution. For this reason, there has been an increased demand in designing packaging materials from biodegradable ingredients such as edible proteins and polysaccharides. In the current study, biodegradable coatings from gelatin (Gel) or gelatin−rice starch (Gel-RS) mixtures were applied to fresh-cut Colocasia (Colocasia esculenta) and potato (Solanum tuberosum) samples, and main quality properties such as weight loss, firmness, breaking force, and color were evaluated during storage for seven days at 5 °C. Gel-coated potato samples kept moisture at higher levels compared to untreated samples or Gel-RS-coated samples (weight loss 41.40 ± 3.33%), while no differences in weight loss were observed for all fresh-cut Colocasia samples. Furthermore, the gelatin−rice starch coating increased the breaking force (1181.40 ± 159.73) and hardness (1609.6 ± 76.79) of fresh-cut potato samples during storage conditions. On the other hand, fresh-cut Colocasia coated with gelatin and gelatin/rice starch showed no significant differences in weight loss and texture characteristics. In conclusion, gelatin and gelatin/rice starch coatings provoke preservation of quality characteristics during storage of fresh-cut potatoes but have no preservation effects on fresh-cut Colocasia. This research enriches the knowledge of the effects of biodegradable coatings on fresh-cut starchy tubers.