The polymyxin antibiotic colistin has been used in decades for treatment and prevention of infectious diseases in livestock. Nowadays, it is even considered as last-line treatment option for severe human infections caused by multidrug- and carbapenem-resistant Gram-negative bacteria. Therefore, the discovery of plasmid-mediated mobile colistin resistance (mcr) genes raised major public health concern. The aim of our study was to analyze colistin-resistant Salmonella enterica strains from animals, food, feed and the environment collected at the National Reference Laboratory for Salmonella in Germany on the presence of mcr-1 to mcr-9 genes. Altogether 407 colistin-resistant (MIC >2 mg/L) Salmonella isolates received between 2011 and 2018 were selected and screened by PCR using a published mcr-1 to mcr-5 as well as a newly developed mcr-6 to mcr-9 multiplex PCR protocol. 254 of 407 (62.4%) isolates harbored either mcr-1 (n = 175), mcr-4 (n = 53), mcr-5 (n = 18) or mcr-1 and mcr-9 (n = 8). The number of mcr-positive isolates ranged from 19 (2017) to 64 (2012) per year. WGS revealed that none of our isolates harbored the mcr-9.1 gene. Instead, two novel mcr-9 variants were observed, which both were affected by frameshift mutations and are probably non-functional. The mcr-harboring isolates were mainly derived from animals (77.2%) or food (20.1%) and could be assigned to ten different Salmonella serovars. Many of the isolates were multidrug-resistant. Co-occurrence of mcr-1 and AmpC or ESBL genes was observed in eight isolates. Our findings suggest that mcr genes are widely spread among colistin-resistant Salmonella isolates from livestock and food in Germany. Potential transfer of mcr-harboring isolates along the food chain has to be considered critically.