The ecological and evolutionary factors that drive the emergence and maintenance of variation in mutualistic benefit (i.e. the benefits provided by one partner to another) in mutualistic symbioses are not well understood. In this study we evaluated the role that host and symbiont phylogeny might play in determining patterns of mutualistic benefit (host response) for interactions among nine species of Acacia and 31 strains of nitrogen-fixing rhizobial bacteria. Using phylogenetic comparative methods we compared patterns of variation in mutualistic benefit to rhizobial phylogenies constructed from housekeeping and symbiosis genes; and a multi-gene host phylogeny. We found widespread genotype-by-genotype variation in patterns of plant growth. A relatively large component of this variation (21-28%) was strongly influenced by the interacting evolutionary histories of both partners, such that phylogenetically similar host species had similar growth responses when inoculated with phylogenetically similar rhizobia. We also found a relatively large non-phylogenetic effect for the average mutualistic benefit provided by rhizobia to plants, such that phylogenetic relatedness did not predict the overall benefit provided by rhizobia across all hosts. We conclude that phylogenetic relatedness should frequently predict patterns of mutualistic benefit in acacia-rhizobial mutualistic interactions; but that some mutualistic traits also evolve independently of the phylogenies.