Gene body methylation (gbM) is an ancestral and widespread feature in Eukarya, yet its adaptive value and evolutionary implications remain unresolved. The occurrence of gbM within protein-coding sequences is particularly puzzling, because methylation causes cytosine hypermutability and hence is likely to produce deleterious amino acid substitutions. We investigate this enigma using an evolutionarily basal group of Metazoa, the stony corals (order Scleractinia, class Anthozoa, phylum Cnidaria). We show that patterns of coral gbM are similar to other invertebrate species, predicting wide and active transcription and slower sequence evolution. We also find a strong correlation between gbM and codon bias, resulting from systematic replacement of CpG bearing codons. We conclude that gbM has strong effects on codon evolution and speculate that this may influence establishment of optimal codons.