Evolvability is an emergent hallmark of cancer that depends on intra-tumor heterogeneity and genetic variation. Mutations generated by APOBEC3 contribute to genetic variation and tumor evolvability. However, the influence of APOBEC3 on the evolvability of the genome and its differential impact on cancer genes versus non-cancer genes remains unclear. Analyzing over 40,000 human protein-coding transcripts, we identified distinct distribution patterns of APOBEC3A/B TC motifs between cancer and non-cancer genes, suggesting unique associations with cancer. Studying a bat species with numerous APOBEC3 genes, we found distinct motif patterns in orthologs of cancer genes compared to non-cancer genes, as in humans, suggesting APOBEC3 evolution to reduce impacts on the genome rather than the converse. Simulations confirmed that APOBEC3-induced heterogeneity enhances cancer evolution through bimodal patterns of mutations in certain classes of genes. Our results suggest the bimodal distribution of APOBEC-induced mutations can significantly increase cancer heterogeneity.