Plant traits are influenced by herbivore diet selection, but little is known about how traits are affected by different types of herbivores. We related eight traits of 27 subalpine shrub species in South Island, New Zealand, to damage of these shrubs by introduced red deer (Cervus elaphus) and native invertebrate herbivores using phylogenetically explicit modeling. Deer preferentially consumed species that grew quickly, were low in foliar tannins, or had high leaf area per unit mass. However, these traits did not trade off against each other; rather, they could be related to different multivariate defense strategies. Although the proportion of leaves damaged by leaf-chewing invertebrates also increased with stem growth, invertebrates did not damage the same fast growing species as those preferred by deer. Other traits may also be important in determining herbivore preferences, as suggested by the high proportion of variation in herbivory explained by phylogeny. Last, we found that the composition of invertebrate herbivore communities was more similar among closely related shrubs, and consequently, the range of invertebrate-plant associations may change if introduced deer shift plant composition toward slow-growing species. Overall, our results demonstrate the importance of herbivore type and coevolved interactions for the adaptive significance of plant traits.