Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Cleaner birds remove ectoparasites and also feed on wounded tissue from herbivorous mammals, an association well known between oxpeckers (genus Buphagus) and ungulates in Africa. I report here on Black Vultures (Coragyps atratus) cleaning capybaras (Hydrochoerus hydrochaeris) in southeastern Brazil, and postulate a sequence of steps that might have given origin to cleaning in omnivorous scavenging birds. The first step would be the familiarity these scavengers have with carcasses, from which they remove small tisues pieces and organic debris, and parasites, followed by a few intermediate steps with behavioural adjustments between the cleaners and their clients, and culminating in cleaning symbiosis with medium to large herbivorous mammals. Moreover, four instances of tick-removal by birds (Molothrus oryzivorus, Milvago chimachima, Machetornis rixosa and Crotophaga ani) from medium to large herbivorous mammals are described, and a list of 12 species of tick-removing birds recorded for Brazil is presented. The similarity between the habits of cathartid vultures and Caracarini falcons is pointed out, tick-removing being recorded for both groups. I suggest that species of Phalcoboenus (Falconidae) and Cyanocorax (Corvidae) might be potential cleaners. Parasite-removing birds are here grouped in two broad categories that would accommodate additional records of this type: 1) omnivorous scavengers and widely foraging birds that dwell in the open and associate with capybaras, wild ungulates, and/or livestock; and 2) largely insectivorous, widely foraging birds that dwell in the open and which also associate with capybaras, wild ungulates, and/or livestock. The exceptions to these two groups would be Ibycter americanus e Psophia leucoptera, respectively, as both species are forest-dwellers.153417426Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)