Aphids harbour an obligatory symbiont, Buchnera aphidicola, providing essential amino acids not supplied by their diet. These bacteria are transmitted vertically and phylogenic analyses suggest that they have 'cospeciated' with their hosts. We investigated this cospeciation phenomenon at a fine taxonomic level, within the aphid genus Brachycaudus. We used DNA-based methods of species delimitation in both organisms, to avoid biases in the definition of aphid and Buchnera species and to infer association patterns without the presumption of a specific interaction. Our results call into question certain 'taxonomic' species of Brachycaudus and suggest that B. aphidicola has diversified into independently evolving entities, each specific to a 'phylogenetic' Brachycaudus species. We also found that Buchnera and their hosts simultaneously diversified, in parallel. These results validate the use of Buchnera DNA data for inferring the evolutionary history of their host. The Buchnera genome evolves rapidly, making it the perfect tool for resolving ambiguities in aphid taxonomy. This study also highlights the usefulness of species delimitation methods in cospeciation studies involving species difficult to conceptualize--as is the case for bacteria--and in cases in which the taxonomy of the interacting organisms has not been determined independently and species definition depends on host association.