Archaeological and genetic analyses of seed-propagated annual crops have greatly advanced our understanding of plant domestication and evolution. Comparatively little is known about perennial plant domestication, a relevant topic for understanding how genes and genomes evolve in long-lived species, and how perennials respond to selection pressures operating on a relatively short time scale. Here, we focus on long-lived perennial crops (mainly trees and other woody plants) grown for their fruits. We reviewed (1) the basic biology of long-lived perennials, setting the stage for perennial domestication by considering how these species evolve in nature; (2) the suite of morphological features associated with perennial fruit crops undergoing domestication; (3) the origins and evolution of domesticated perennials grown for their fruits; and (4) the genetic basis of domestication in perennial fruit crops. Long-lived perennials have lengthy juvenile phases, extensive outcrossing, widespread hybridization, and limited population structure. Under domestication, these features, combined with clonal propagation, multiple origins, and ongoing crop-wild gene flow, contribute to mild domestication bottlenecks in perennial fruit crops. Morphological changes under domestication have many parallels to annual crops, but with key differences for mating system evolution and mode of reproduction. Quantitative trait loci associated with domestication traits in perennials are mainly of minor effect and may not be stable across years. Future studies that take advantage of genomic approaches and consider demographic history will elucidate the genetics of agriculturally and ecologically important traits in perennial fruit crops and their wild relatives.