The current study aimed obtaining antimicrobial sachets that could be used as preservatives for foods. Basil (BEO) and Pimenta dioica (PDEO) essential oils (EOs) were analyzed by GC-FID and GC-MS and tested against the foodborne bacteria S. aureus, E. coli, L. monocytogenes, P. aeruginosa, S. Enteritidis, and the food-spoilage mold B. nivea. Then, inclusion complexes (ICs) with EOs and β-cyclodextrin (β-CD) were prepared as a strategy to reduce volatility and increase the release time of EOs. Eight ICs were prepared by kneading and freeze-drying methods, in two molar ratios, and have been characterized by complementary methods: FT-IR, thermal analysis (DSC and TG/DTG), powder XRD, and solid state C NMR. In vitro antimicrobial activities of ICs, both dispersed in agar and loaded in sachets, have also been investigated. Complexation was confirmed for all samples. PDEO-based ICs prepared by kneading method, at both molar ratios, displayed better in vitro antimicrobial activity. The obtained results strongly suggest a potential application of these ICs as natural antimicrobials.