Theory has long predicted that insect community structure should be related to host plant phylogeny. We examined the distribution of insect herbivore associations with respect to host plant phylogeny for caterpillars (Lepidoptera), beetles (Coleoptera), and grasshoppers and relatives (orthopteroids) in a New Guinea rain forest. We collected herbivores from three lineages of closely related woody plants and from more distantly related plant lineages in the same locality to examine the phylogenetic scale at which host specificity can be detected in a community sample. By grafting molecular phylogenies inferred from three different genes into a supertree, we developed a phylogenetic hypothesis for the host community. Feeding experiments were performed on more than 100 000 live insects collected from the 62 host species. We examined patterns of host use with respect to the host plant phylogeny. As predicted, we found a negative relationship between faunal similarity, defined as the proportion of all herbivores feeding on two hosts that are shared between the hosts, and the phylogenetic distance between hosts based on DNA sequence divergence. Host phylogenetic distance explained a significant fraction of the variance (25%) in herbivore community similarity, in spite of the many ecological factors that probably influence feeding patterns. Herbivore community similarity among congeneric hosts was high (50% on average) compared to overlap among host families (20-30% on average). We confirmed this pattern using the nearest taxon index (NTI) and net relatedness index (NRI) to quantify the extent of phylogenetic clustering in particular herbivore associations and to test whether patterns are significantly different from chance expectations. We found that 40% of caterpillar species showed significant phylogenetic clustering with respect to host plant associations, somewhat more so than for beetles or orthopteroids. We interpret this as evidence that a substantial fraction of tropical forest insect herbivores are clade specialists.