The adherens junction couples the actin cytoskeletons of neighboring cells to provide the foundation for multicellular organization. The core of the adherens junction is the cadherin-catenin complex that arose early in the evolution of multicellularity to link actin to intercellular adhesions. Over time, evolutionary pressures have shaped the signaling and mechanical functions of the adherens junction to meet specific developmental and physiological demands. Evolutionary rate covariation (ERC) identifies proteins with correlated fluctuations in evolutionary rate that can reflect shared selective pressures and functions. Here we use ERC to identify proteins with evolutionary histories similar to the Drosophila E-cadherin (DE-cad) ortholog. Core adherens junction components α-catenin and p120-catenin displayed positive ERC correlations with DE-cad, indicating that they evolved under similar selective pressures during evolution between Drosophila species. Further analysis of the DE-cad ERC profile revealed a collection of proteins not previously associated with DE-cad function or cadherin-mediated adhesion. We then analyzed the function of a subset of ERC-identified candidates by RNAi during border cell (BC) migration and identified novel genes that function to regulate DE-cad. Among these, we found that the gene CG42684, which encodes a putative GTPase activating protein (GAP), regulates BC migration and adhesion. We named CG42684 raskol ("to split" in Russian) and show that it regulates DE-cad levels and actin protrusions in BCs. We propose that Raskol functions with DE-cad to restrict Ras/Rho signaling and help guide BC migration. Our results demonstrate that a coordinated selective pressure has shaped the adherens junction and this can be leveraged to identify novel components of the complexes and signaling pathways that regulate cadherin-mediated adhesion.