Antimicrobial resistance against colistin has emerged worldwide and is threatening the efficacy of colistin treatment of multi-resistant Gram-negative bacteria. In this study, PCRs were used to detect mcr genes (mcr-1, mcr-2, mcr-3) in 213 anal and 1,339 nasal swabs from pigs (n = 1,454) in nine provinces of China, and 1,696 cloacal and 1,647 oropharyngeal samples from poultry (n = 1,836) at live-bird markets in 24 provinces. The mcr-1 prevalences in pigs (79.2%) and geese (71.7%) were significantly higher than in chickens (31.8%), ducks (34.6%) and pigeons (13.1%). The mcr-2 prevalence in pigs was 56.3%, significantly higher than in chickens (5.5%), ducks (2.3%), geese (5.5%) and pigeons (0%). The mcr-3 prevalences in pigs (18.7%), ducks (13.8%) and geese (11.9%) were significantly higher than in chickens (5.2%) and pigeons (5.1%). In total, 173 pigs and three chickens were positive for all three mcr genes. The prevalences of the mcr were significantly higher in nasal/oropharyngeal swabs than in the anal /cloacal swabs. Phylogenetic studies identified 33 new mcr-2 variants and 12 new mcr-3 variants. This study demonstrates high prevalences of mcr in pigs and poultry in China, and indicates there is need for more thorough surveillance and control programs to prevent further selection of colistin resistance.