Synthetic chemical preservatives are widely used in the food industry to delay the deterioration caused by microbial growth, enzyme activities and oxidation reactions. The last few decades have witnessed marked interest in finding natural food preservatives due to the potential health damage of synthetic preservatives; consumers have become skeptical of consuming foods containing these additives. Polyphenols used as natural preservatives that can be extracted from fruits, vegetables, herbs and spices provide the best alternative for partial or complete replacement of their synthetic analogues. The present study’s emphasis was on employing different plant extracts to be efficiently used as antimicrobial agents for developing replacements for the synthetic chemical additives in food products. The study also investigated the antimicrobial potentialities of five medicinal plants, widely used in Egypt (sumac, tamarind, rosemary, roselle and lemon) against six microbial markers (E. coli, P. aeruginosae, B. subtilis, S. aureus, Penicillium sp. and A. niger.). Sumac extracts showed the best activity against all tested microorganisms, producing the widest inhibition zones ranging from 14 to 45 mm, followed by tamarind and roselle extracts, with inhibition zones ranging from 8–36 and 8–34 mm, respectively. On the other hand, extracts of rosemary and lemon showed variable antimicrobial activity. All extracts from all tested plants were less active against fungal species than bacterial species. In all cases, the organic extracts (80% methanol, 80% ethanol) showed the same or greater activity than the aqueous extracts. In addition, the methanolic extracts showed the strongest and broadest spectrum. The most sensitive strain to plant extracts was B. subtilis, while the most resistant strain was P. aeruginosae. The MIC and MBC or MFC values of methanolic extracts were assayed using the broth dilution method. Sumac extract showed the best activity against all tested microorganisms with the lowest values of MIC and MBC or MFC (from 0.260 to 0.877 and 0.310 to 1.316 mg/mL, respectively, for bacteria, and from 1.975 to 2.5 and 2.5 to 4.444 mg/mL, respectively, for fungi). Interestingly, the tested extracts inhibited microbial growth in tomato paste and pasteurized cow milk for a long storage period (increase shelf life) as compared to the control samples. In conclusion, herbal and spice extracts could be successfully applied as natural antimicrobials for the elimination of food borne microbes and pathogen growth.