Despite the prevalence of sexual reproduction across eukaryotes, there is a remarkable diversity of sex-determination mechanisms. The underlying causes of this diversity remain unclear, and it is unknown whether there are convergent trends in the directionality of turnover in sex-determination mechanisms. We used the recently assembled Tree of Sex database to assess patterns in the evolution of sex-determination systems in the remarkably diverse vertebrate clades of teleost fish, squamate reptiles and amphibians. Contrary to theoretical predictions, we find no evidence that the evolution of separate sexes is irreversible, as transitions from separate sexes to hermaphroditism occur at higher rates than the reverse in fish. We also find that transitions from environmental sex determination to genetic sex determination occur at higher rates than the reverse in both squamates and fish, suggesting that genetic sex determination is more stable. However, our data are not consistent with the hypothesis that heteromorphic sex chromosomes are an "evolutionary trap." Rather, we find similar transition rates between homomorphic and heteromorphic sex chromosomes in both fish and amphibians, and to environmental sex determination from heteromorphic vs. homomorphic sex chromosome systems in fish. Finally, we find that transitions between male and female heterogamety occur at similar rates in amphibians and squamates, while transitions to male heterogamety occur at higher rates in fish. Together, these results provide the most comprehensive view to date of the evolution of vertebrate sex determination in a phylogenetic context, providing new insight into long-standing questions about the evolution of sexual reproduction. © 2018 John Wiley & Sons Ltd.