Despite recent advances in the understanding of morphological evolution, the genetic underpinnings of behavioral and physiological evolution remain largely unknown. Here, we study the metabolic changes that evolved in independently derived populations of the Mexican cavefish, Astyanax mexicanus. A hallmark of cave environments is scarcity of food. Cavefish populations rely almost entirely on sporadic food input from outside of the caves. To survive under these conditions, cavefish have evolved a range of adaptations, including starvation resistance and binge eating when food becomes available. The use of these adaptive strategies differs among independently derived cave populations. Although all cavefish populations tested lose weight more slowly than their surface conspecifics during restricted rations, only a subset of cavefish populations consume more food than their surface counterparts. A candidate gene-based screen led to the identification of coding mutations in conserved residues of the melanocortin 4 receptor (MC4R) gene, contributing to the insatiable appetite found in some populations of cavefish. Intriguingly, one of the mutated residues has been shown to be linked to obesity in humans. We demonstrate that the allele results in both reduced maximal response and reduced basal activity of the receptor in vitro. We further validate in vivo that the mutated allele contributes to elevated appetite, growth, and starvation resistance. The allele appears to be fixed in cave populations in which the overeating phenotype is present. The presence of the same allele in multiple caves appears to be due to selection from standing genetic variation present in surface populations.