Multidrug-resistant (MDR) Gram-negative pathogens, especially Acinetobacter baumannii, Pseudomonas aeruginosa, Escherichia coli and Enterobacter spp., are recognized by the World Health Organization as the most critical priority pathogens in urgent need of drug development. In this study, the in vitro antimicrobial activity of robenidine analogues NCL259 and NCL265 was tested against key human and animal Gram-negative clinical isolates and reference strains. NCL259 and NCL265 demonstrated moderate antimicrobial activity against these Gram-negative priority pathogens with NCL265 consistently more active, achieving lower minimum inhibitory concentrations (MICs) in the range of 2–16 µg/mL. When used in combination with sub-inhibitory concentrations of polymyxin B to permeabilize the outer membrane, NCL259 and NCL265 elicited a synergistic or additive activity against the reference strains tested, reducing the MIC of NCL259 by 8- to 256- fold and the MIC of NCL265 by 4- to 256- fold. A small minority of Klebsiella spp. isolates (three) were resistant to both NCL259 and NCL265 with MICs > 256 µg/mL. This resistance was completely reversed in the presence of the efflux pump inhibitor phenylalanine-arginine-beta-naphthylamide (PAβN) to yield MIC values of 8–16 µg/mL and 2–4 µg/mL for NCL259 and NCL256, respectively. When NCL259 and NCL265 were tested against wild-type E. coli isolate BW 25113 and its isogenic multidrug efflux pump subunit AcrB deletion mutant (∆AcrB), the MIC of both compounds against the mutant ∆AcrB isolate was reduced 16-fold compared to the wild-type parent, indicating a significant role for the AcrAB-TolC efflux pump from Enterobacterales in imparting resistance to these robenidine analogues. In vitro cytotoxicity testing revealed that NCL259 and NCL265 had much higher levels of toxicity to a range of human cell lines compared to the parent robenidine, thus precluding their further development as novel antibiotics against Gram-negative pathogens.