Food-borne pathogens such as Escherichia coli (E. coli) and Staphylococcus aureus (S. aureus) create a lot of problems worldwide and are a major concern of food producers and consumers. To protect the food from spoilage due to these bacteria, antimicrobial packaging is one of the most promising active packaging systems. Environmental concerns associated with plastic waste emphasized the development of packaging films from natural polymers such as starch. Therefore, in the present study, potato starch-based biodegradable and antimicrobial nanocomposite films were prepared with constant concentration of zinc oxide nanoparticles using casting method. Films were prepared using three antimicrobial agents, cinnamon oil, clove oil, and potassium sorbate and were tested against four microbes, S. aureus, E. coli, Salmonella typhi (S. typhi), and Campylobacter jejuni (C. jejuni). The films prepared with clove oil were most effective against S. aureus (22–100% inhibition), those prepared with cinnamon oil were effective against C. jejuni (19–22% inhibition) and growth of E. coli was inhibited (33–40% inhibition) to maximum extent by potassium sorbate incorporated films. However, for complete inhibition of C. jejuni and E. coli, higher concentrations of cinnamon oil and potassium sorbate are required. Increasing concentration of antimicrobial agents decreased the tensile strength of the films. Tensile strength decreased up to 13% in cinnamon oil films, 23% in clove oil films and up to 34% in potassium sorbate incorporated films. Based on the results, it can be concluded that cinnamon oil is a better antimicrobial agent due to its least effect on tensile strength and also due to its antibacterial effect against the three bacteria.