Antimicrobial resistance against colistin has emerged worldwide threatening the efficacy of one of the last-resort antimicrobials used for the treatment of Enterobacteriaceae. To investigate the presence of the recently identified colistin resistance genes (mcr-4, mcr-5) in China, we established PCRs to detect mcr-4 and mcr-5 on 213 anal and 1,339 nasal swabs from apparently healthy pigs (n = 1,454) in nine provinces, and 1,696 cloacal and 1,647 oropharyngeal samples from poultry (n = 1,836) at live-bird markets in 24 provinces of China. The prevalence of the mcr-4 in swine swabs (41.4%; 642/1,552) was significantly higher than in swabs from poultry (11.5%; 384/3,343). The mcr-4 gene was found in geese (49.5%, 54/109), chickens (17.2%, 257/1,498), pigeons (17.2%, 17/99) and ducks (15.4%, 20/130). In a similar trend, the prevalence of the mcr-5 in swine swabs (33.1%; 514/1552) was significantly higher than in swabs from poultry (5.6%; 187/3,343). The mcr-5 was identified in geese (17.4%, 19/109), chickens (9.9%, 148/1,498), ducks (7.7%, 10/130) and pigeons (3%, 3/99). The mcr-4 prevalence in the nasal swabs from pigs (59.2%, 58/98) was significantly higher than that in anal swabs (29.6%, 29/98) (P<0.001). Similarly, the mcr-5 prevalence in the nasal swabs from pigs (61.2%, 60/98) was significantly higher than in anal swabs (44.9%, 44/98) (P = 0.02), and significantly higher in oropharyngeal swabs (7.2%, 109/1,507) than in the cloacal swabs (3.7%, 56/1,507) (P<0.001). This study further confirms the presence of the mcr-4 and mcr-5 in animals and indicates these genes are prevalent and widespread in food producing animals (pig and poultry) in China. Future studies are needed to characterize the bacteria carrying the mcr-4 and mcr-5 and their locations on plasmids and/or the bacterial chromosomes, and determine co-resistances in the mcr-4 and mcr-5 positive strains.