Understanding the driving forces and molecular processes underlying dioecy and sex chromosome evolution, leading from hermaphroditism to the occurrence of male and female individuals, is of considerable interest in fundamental and applied research. The genus Phoenix, belonging to the family Arecaceae, consists of only dioecious species. Phylogenetic data suggests that the genus Phoenix diverged from a hermaphroditic ancestor shared with its closest relatives. Here we investigated the evolution of suppressed recombination within the genus Phoenix as a whole by extending the analysis of P. dactylifera sex-related loci to eight other species within the genus. We also performed a phylogenetic analysis of a date palm sex-linked PdMYB1 gene in these species. We found that X and Y sex-linked alleles clustered in a species-independent fashion. Our data show that sex chromosomes evolved before the diversification of the extant dioecious species. Furthermore, the distribution of Y haplotypes revealed two male ancestral paternal lineages which may have emerged prior to speciation.