Bacterial endosymbionts evolve under strong host-driven selection. Factors influencing host evolution might affect symbionts in similar ways, potentially leading to correlations between the molecular evolutionary rates of hosts and symbionts. Although there is evidence of rate correlations between mitochondrial and nuclear genes, similar investigations of hosts and symbionts are lacking. Here we demonstrate a correlation in molecular rates between the genomes of an endosymbiont (Blattabacterium cuenoti) and the mitochondrial genomes of their hosts (cockroaches). We used partial genome data for multiple strains of B. cuenotito compare phylogenetic relationships and evolutionary rates for 55 cockroach/symbiont pairs. The phylogenies inferred for B. cuenoti and the mitochondrial genomes of their hosts were largely congruent, as expected from their identical maternal and cytoplasmic mode of inheritance. We found a correlation between evolutionary rates of the two genomes, based on comparisons of root-to-tip distances and on comparisons of branch lengths of phylogenetically independent species pairs. Our results underscore the profound effects that long-term symbiosis can have on the biology of each symbiotic partner.