Edible coatings with antimicrobial agents can extend the shelf-life of fresh-cut fruit. The effect of lemongrass, oregano oil and vanillin incorporated in apple puree-alginate edible coatings, on the shelf-life of fresh-cut ‘Fuji’ apples, was investigated. Coated apples were packed in air filled polypropylene trays and wrapped with polypropylene film. Changes in headspace atmosphere, color, firmness, sensory quality and microbial growth were measured during 21 days storage at 4 °C. A significant reduction in the rates of O2 depletion and CO2 production was observed in samples containing high concentrations of essential oils. Ethylene production in the coated apples remained below 50 μL L−1, while production of this gas increased continuously in uncoated apples and those coated without essential oils during storage. Apples coated with apple puree-alginate exhibited ethanol and acetaldehyde formation in the first week. Coatings with calcium chloride and N-acetylcysteine helped to maintain firmness and color, while lemongrass containing coatings induced severe texture softening. Vanillin containing coatings (0.3% w/w) were the most effective in terms of sensory quality after 2 weeks storage. All antimicrobial coatings significantly inhibited the growth of psychrophilic aerobes, yeasts and molds. The antimicrobial effect of essential oils against L. innocua inoculated into apple pieces before coating was also examined. Lemongrass (1.0 and 1.5% w/w) and oregano oil containing coatings (0.5% w/w) exhibited the strongest antimicrobial activity against L. innocua (4 log reduction).