Antimicrobial resistance is a global health concern across the world and it is foreseen to swell if no actions are taken now. To help curbing this well announced crisis different strategies are announced, and these include the use of antimicrobial peptides (AMP), which are remarkable molecules known for their killing activities towards pathogenic bacteria. Bacteriocins are ribosomally synthesized AMP produced by almost all prokaryotic lineages. Bacteriocins, unlike antibiotics, offer a set of advantages in terms of cytotoxicity towards eukaryotic cells, their mode of action, cross-resistance and impact of microbiota content. Most known bacteriocins are produced by Gram-positive bacteria, and specifically by lactic acid bacteria (LAB). LAB-bacteriocins were steadily reported and characterized for their activity against genetically related Gram-positive bacteria, and seldom against Gram-negative bacteria. The aim of this study is to show that lacticaseicin 30, which is one of the bacteriocins produced by Lacticaseibacillus paracasei CNCM I-5369, is active against Gram-negative clinical strains (Salmonella enterica Enteritidis H10, S. enterica Typhimurium H97, Enterobacter cloacae H51, Escherichia coli H45, E. coli H51, E. coli H66, Klebsiella oxytoca H40, K. pneumoniae H71, K. variicola H77, K. pneumoniae H79, K. pneumoniae H79), whereas antibiotics failed. In addition, lacticaseicin 30 and colistin enabled synergistic interactions towards the aforementioned target Gram-negative clinical strains. Further, the combinations of lacticaseicin 30 and colistin prompted a drastic downregulation of mcr-1 and mcr-9 genes, which are associated with the colistin resistance phenotypes of these clinical strains. This report shows that lacticaseicin 30 is active against Gram-negative clinical strains carrying a rainbow of mcr genes, and the combination of these antimicrobials constitutes a promising therapeutic option that needs to be further exploited.