Increasing strawberry consumption has led to a growing safety concern because they are not washed after harvest. An antimicrobial edible coating could be an effective postharvest technique to ensure microbial safety and, at the same time, retain overall quality of the fruits. Response surface methodology was used to optimize the antimicrobial activity against Escherichia coli O157:H7 and Botrytis cinerea and several physical properties (turbidity, viscosity, and whitish index) of an alginate coating. A full factorial design was used to select the concentrations of carvacrol and methyl cinnamate on the basis of their effect against E. coli and B. cinerea. A central composite design was then performed to evaluate the effects/interactions of the two antimicrobials on the coating characteristics. The results from analysis of variance showed the significant fitting of all responses to the quadratic model. To attain the desirable responses, the optimal concentrations were 0.98% (w/w) carvacrol and 1.45% (w/w) methyl cinnamate.