The coevolution trends of amino acids within or between genes offer key insights into protein structure and function. Existing tools for uncovering coevolutionary signals primarily rely on multiple sequence alignments, often overlooking phylogenetic relatedness and shared evolutionary history. Here, we introduce PHACE, a phylogeny-aware coevolution algorithm that maps amino acid substitutions onto a phylogenetic tree to detect molecular coevolution. PHACE categorizes amino acids at each position into “tolerable” and “intolerable” groups, based on their independent recurrence across the tree, reflecting a position’s tolerance to specific substitutions. Gaps are treated as a third character type, with only phylogenetically independent gap changes considered. The method computes substitution scores per branch by traversing the tree and quantifying probability differences across adjacent nodes for each group. To avoid artifacts from alignment errors, we apply a multiple sequence alignment–masking procedure. Compared to phylogeny-based methods (CAPS, CoMap) and state-of-the-art multiple sequence alignment–based approaches (DCA, GaussDCA, PSICOV, mutual information), PHACE shows significantly superior accuracy in identifying coevolving residue pairs, as measured by statistical metrics including Matthews correlation coefficient, area under the ROC curve, and F1 score. This performance stems from PHACE’s explicit modeling of phylogenetic dependencies, often ignored in coevolution analyses.