It remains a major challenge to identify the genes and mutations that lead to plant sexual differentiation. Here, we study the structure and evolution of the sex-determining region (SDR) in Vitis species. We report an improved, chromosome-scale Cabernet Sauvignon genome sequence and the phased assembly of nine wild and cultivated grape genomes. By resolving twenty Vitis SDR haplotypes, we compare male, female, and hermaphrodite haplotype structures and identify sex-linked regions. Coupled with gene expression data, we identify a candidate male-sterility mutation in the VviINP1 gene and potential female-sterility function associated with the transcription factor VviYABBY3. Our data suggest that dioecy has been lost during domestication through a rare recombination event between male and female haplotypes. This work significantly advances the understanding of the genetic basis of sex determination in Vitis and provides the information necessary to rapidly identify sex types in grape breeding programs.