Xanthorrhizol (XTZ), isolated from Curcuma xanthorrhiza, has potent antifungal and antibacterial activity. It shows very strong activity against Gram-positive bacteria, such as Streptococcus mutans and Staphylococcus aureus, but is generally not active against Gram-negative bacteria. In this study, we explored the possibility of using a combination strategy for expanding the antimicrobial spectrum of XTZ against Gram-negative bacteria. To take advantage of XTZ being a food-grade material, 10 food-grade or generally recognized as safe (GRAS) antimicrobial compounds with low toxicities were selected for combination therapy. In addition, polymyxin B nonapeptide (PMBN), which is less toxic than polymyxin B, was also selected as an outer membrane permeabilizer. The antibacterial activity of various double or triple combinations with or without XTZ were assayed in vitro against four Gram-negative bacterial species (Escherichia coli, Salmonella enterica serovar Typhi, Salmonella enterica serovar Typhimurium, and Vibrio cholerae), with synergistic combinations exhibiting clear activity subjected to further screening. The combinations with the greatest synergism were XTZ + PMBN + nisin, XTZ + PMBN + carvacrol, and XTZ + PMBN + thymol. These combinations also showed potent antimicrobial activity against Shigella spp., Yersinia enterocolitica, and Acinetobacter baumannii. In time-kill assays, the three combinations achieved complete killing of E. coli within 2 h, and S. Typhi and V. cholera within 15 min. This is the first report on expanding the activity spectrum of XTZ against Gram-negative bacteria through combination with PMBN and food-grade or GRAS substances, with the resulting findings being particularly useful for increasing the industrial and medical applications of XTZ.