Mango (Manguifera indica var. Azúcar) is known for its distinctive aroma and flavor that contrast with a short shelf life due to the fruit being highly perishable; thus, it is necessary to find mechanisms that help us extend its shelf life. Currently, the use of biopolymers obtained from plant sources as biodegradable, renewable, and low-cost materials for food packaging, combined with the use of essential oils obtained from plant matrices, is capable of improving mangoes' antioxidant, antimicrobial, and barrier properties. We evaluated the effect of the application of a composite edible coating from cassava–Arabic gum incorporated with oregano essential oil for the preservation of fresh-cut mango. A composite edible coating was prepared with different concentrations of cassava hydrocolloids (4, 6, and 8% w), Arabic gum (1%), and oregano essential oil (0.25 and 0.5% v/v). The physical properties of the coating solution were analyzed (color, rheology, and microstructure). Then, the composite edible coating was applied by dipping fresh-cut slices of mango into it, and these were stored for 30 days. The water loss, pH, titratable acidity, total solids, and color were evaluated. The experimental data were adjusted to a zero-order kinetic model. The composite edible coating solution presented non-Newtonian shear thinning behavior described by the Carreau–Yasuda model. Coated mango pieces with the highest addition of essential oil demonstrated a decrease of up to 10% in water loss rate and improved preservation of total solids and acidity, leading to a lower difference in color (ΔE) compared to the uncoated sample for up to 30 days. The results suggest that the application of this coating can extend the shelf life of this minimally processed product.