The antimicrobial activity against Escherichia coli and Listeria innocua of nanoemulsions containing oregano, thyme, lemongrass or mandarin essential oils and high methoxyl pectin was assessed during a long-term storage period (56 days). On one hand, a higher antimicrobial activity was detected against E. coli compared to L. innocua regardless the EO type. Transmission Electron Microscopy (TEM) images showed a significant damage in the E. coli cells for both the cytoplasm and cytoplasmic membrane, led to cell death. The antimicrobial activity of the nanoemulsions was found to be strongly related to the EO type rather than to their droplet size. The lemongrass-pectin nanoemulsion had the smallest droplet size (11 ± 1 nm) and higher antimicrobial activity reaching 5.9 log reductions of the E. coli population. Nevertheless, the freshly made oregano, thyme and mandarin EO-pectin nanoemulsion led to 2.2, 2.1 or 1.9 E. coli log-reductions, respectively. However, the antimicrobial activity decreased significantly during storage regardless the EO type, which was related to the loss of volatile compounds over time according to our results. The current work provides valuable information in order to make progress in the use of nanoemulsions containing EOs as decontaminating agents in food products.