Developing microbicides for topical epithelial applications is extremely challenging, as evidenced by the scarcity of approved products even after decades of research. Chemical enhancers, including surfactants, are known to be effective antimicrobial agents but are typically toxic towards epithelial cells. Here, we report on the discovery of unique surfactant formulations with improved safety and efficacy profile for epithelial applications, via a combination of high throughput screening techniques. Over three-hundred formulations derived from nine surfactants were screened for antibacterial properties against E. coli in vitro. A subset of these formulations showed high antibacterial activity and was screened for cytotoxicity in vitro. Formulations showing high antibacterial activity and reduced cytotoxicity compared to their individual components were tested for efficacy against B. thailendensis, a model for melioidosis-causing B. pseudomallei. Lead formulations showed lower toxicity towards epidermal keratinocytes, with LC50 values up to 3.5-fold higher than their component surfactants, while maintaining antibacterial efficacy against B. thailendensis. Our results demonstrate that such a combinatorial screening approach can be used for designing safe and potent microbicides for epithelial applications.