Celery (Apium graveolens L.) is an important vegetable crop in the Apiaceae family. It comprises three botanical varieties: common celery with solid and succulent petioles, celeriac or root celery with enlarged and fleshy hypocotyls and smallage or leaf celery with slender, leafy and usually hollow petioles. Here we present a chromosome-level genome assembly of a celeriac cultivar and a comprehensive genome variation map constructed through resequencing of 177 representative celery accessions. Phylogenetic analysis revealed that smallage from the Mediterranean region represented the most ancient type of cultivated celery. Following initial domestication in this region, artificial selection has primarily aimed at enlarging the hypocotyl, resulting in celeriac, and at solidifying the petiole, leading to common celery. Selective sweep analysis and genome-wide association study identified several genes associated with hypocotyl expansion and revealed that the hollow/solid petiole trait directly correlated with the presence/absence of a NAC gene. Our study elucidates the complex breeding history of celery and provides valuable genomic resources and molecular insights for future celery improvement and conservation efforts.