Conserved interactions among proteins or other molecules can provide strong evidence for coevolution across their evolutionary history. Diverse phylogenetic methods have been applied to identify potential coevolutionary relationships. In most cases, these methods minimally require comparisons of orthologous sequences and appropriate controls to separate effects of selection from the overall evolutionary relationships. In vertebrates, androgen receptor (AR) and cytochrome p450 aromatase (CYP19) share an affinity for androgenic steroids, which serve as receptor ligands and enzyme substrates. In a recent study, Tiwary and Li (Tiwary BK, Li W-H. 2009. Parallel evolution between aromatase and androgen receptor in the animal kingdom. Mol Biol Evol. 26:123-129) reported that AR and CYP19 displayed a signature of ancient and conserved interactions throughout all the Eumetazoa (i.e., cnidarians, protostomes, and deuterostomes). Because these findings conflicted with a number of previous studies, we reanalyzed the data set used by Tiwary and Li. First, our analyses demonstrate that the invertebrate genes used in the previous analysis are not orthologous sequences but instead represent a diverse set of nuclear receptors and CYP enzymes with no confirmed or hypothesized relationships with androgens. Second, we show that 1) their analytical approach, which measures correlations in evolutionary distances between proteins, potentially led to spurious significant relationships due simply to conserved domains and 2) control comparisons provide positive evidence for a strong influence of evolutionary history. We discuss how corrections to this method and analysis of key taxa (e.g., duplications in the teleost fish and suiform lineages) can inform investigations of the coevolutionary relationships between AR and aromatase.