This study aims to investigate the chemical composition, antioxidant, and antimicrobial activity of two essential oils (EOs) from Algerian propolis. The volatile constituents were analyzed by gas chromatography-mass spectrometry. Fifty components were identified from the oils. The major components were found to be: cedrol (17.0%), β-eudesmol (7.7%), and α-eudesmol (6.7%) in EO of propolis from Oum El Bouaghi (EOPO) whilst α-pinene (56.1%), cis-verbenol (6.0%), and cyclohexene,3-acetoxy-4-(1-hydroxy-1-methylethyl)-1-methyl (4.4%) in EO of propolis from Batna (EOPB). The antioxidant properties of EOPO and EOPB were determined using 2,2′-azino-bis(3-ethylbenzothiazoline-6-sulfonate) (ABTS•+) and cupric reducing antioxidant capacity (CUPRAC assays), respectively. Both EOs had more cupric ion reducing ability than scavenging ABTS•+ radicals. The antimicrobial potential of the two EOs against eight pathogens was assayed by the agar diffusion method and the mode of action was determined by microdilution assay. The results revealed that EOPB was bactericidal for all tested pathogenic bacteria and fungicidal for Candida albicans ATCC 10231, whereas, EOPO showed bacteriostatic effect against Escherichia coli O157:H7 and Pseudomonas aeruginosa ATCC27853 and fungistatic effect against C. albicans ATCC 10231. Thus, the obtained results suggest the important use of propolis EOs as preservative agents.