Bird species in the avian genus Pitohui contain potent neurotoxic alkaloids that may be used for defense. The genus comprises multiple species that are endemic to New Guinea and were presumed to belong to the family Pachycephalidae or Colluricinclidae, within the core corvoidea, an ancient Australasian radiation of crow-like birds. In order to understand the evolution of toxicity within the genus Pitohui, we sequenced three mitochondrial and two nuclear gene segments and reconstructed a phylogeny of the genus Pitohui and its putative relatives. We show that the genus Pitohui is polyphyletic, and consists of five different lineages. Using Bayesian ancestral state reconstruction, we estimate that toxicity likely evolved multiple times within this group. Furthermore, because the morphological and behavioral similarity among these poisonous birds appears to have evolved convergently, we hypothesize that this may be a possible example of Müllerian mimicry in birds. The Morningbird of Palau, Micronesia, that has often been included in the genus Pitohui, actually belongs in the genus Pachycephala and offers an intriguing case of pronounced evolution on a remote oceanic island.