Data of somatic mutation screening of cancer genomes have provided us huge amounts of information for identifying new cancer genes. Current methods for identifying candidate cancer genes based on gene mutation frequencies tend to find cancer genes with high mutation frequencies. However, many genes with low mutation frequencies might also play important roles during tumorigenesis. Based on the assumption that genes with similar phylogenetic profiles and pro-tein-protein interactions might have similar functions and their disruptions might lead to similar disease phenotypes, we proposed a new approach to find candidate cancer genes. First, we searched for protein-protein interaction subnetworks within which proteins have similar phylogenetic profiles, termed as co-evolving gene modules. Then, we identified genes that have at least one non-synonymous mutation in cancer genomes and directly interact with known cancer genes in the same co-evolving gene modules and predicted them as candidate cancer genes. In this way, we found 15 candidate cancer genes, among which only two genes had been identified previously as candidate cancer genes using the methods based on gene mutation frequencies. Thus, the candidate cancer genes with low mutation frequencies can be found by our method.