The geographic origins of breeds and the genetic basis of variation within the widely distributed and phenotypically diverse domestic rock pigeon (Columba livia) remain largely unknown. We generated a rock pigeon reference genome and additional genome sequences representing domestic and feral populations. We found evidence for the origins of major breed groups in the Middle East and contributions from a racing breed to North American feral populations. We identified the gene EphB2 as a strong candidate for the derived head crest phenotype shared by numerous breeds, an important trait in mate selection in many avian species. We also found evidence that this trait evolved just once and spread throughout the species, and that the crest originates early in development by the localized molecular reversal of feather bud polarity.