There is a noticeable interest in alternative therapies where the outcome is the eradication of the Gram-negative bacterium, Helicobacter pylori (H. pylori), for the purpose of treating many stomach diseases (chronic gastritis and peptic ulcers) and preventing stomach cancer. It is especially urgent because the mentioned pathogen infects over 50% of the world’s population. Recent studies have shown the potential of natural products, such as medicinal plant and bee products, on the inhibition of H. pylori growth. Propolis is such a bee product, with known antimicrobial activities. The main scope of the study is the determination of the antimicrobial activity of ethanolic extracts from 11 propolis samples (mostly from Poland, Ukraine, Kazakhstan, and Greece) against H. pylori, as well as selected bacterial and yeast species. The most effective against H. pylori was the propolis from Ukraine, with an MIC = 0.02 mg/mL while the rest of samples (except one) had an MIC = 0.03 mg/mL. Moreover, significant antimicrobial activity against Gram+ bacteria (with an MIC of 0.02–2.50 mg/mL) and three yeasts (with an MIC of 0.04–0.63 mg/mL) was also observed. A phytochemical analysis (polyphenolic profile) of the propolis samples, by ultra-high-performance liquid chromatography-diode array detector-mass spectrometry (UPLC-DAD-MS), was performed. An evaluation of the impact of the propolis components on antimicrobial activity, consisting of statistical analyses (principal component analysis (PCA) and hierarchical fuzzy clustering), was then performed. It was observed that the chemical composition characteristics of the poplar propolis correlated with higher antibacterial activity, while that of the poplar and aspen propolis correlated with weaker antibacterial activity. To summarize the activity in vitro, all tested propolis samples indicate that they can be regarded as useful and potent factors in antimicrobial therapies, especially against H. pylori.