A surprising diversity of mechanisms controls sex determination of vertebrate organisms, even among closely related species. Both genetic and temperature-dependent systems of sex determination have been described in teleost fish. In the common zebrafish model organism, heteromorphic sex chromosomes are not observed, and the potential role of a genetic component of sex determination remains largely unknown. Here we report a genome-wide linkage study of sex determination in zebrafish using a novel SNP genetic map. We identified loci on zebrafish chromosomes 5 (LOD score 7.9) and 16 (LOD score 9.3) governing sex determination as a complex trait, rather than as an XY or ZW genetic system. Each of these loci contains a prominent candidate gene with a conserved role in sex determination across additional species that suggest potential mechanisms of sex determination in zebrafish. The chromosome 5 locus harbors dmrt1, a key gene in sex determination from fruit flies to humans; mutation of the human DMRT1 ortholog is a cause of complete sex reversal of XY individuals. The chromosome 16 locus harbors cyp21a2; mutation of the human CYP21A2 ortholog is one of the more common causes of pseudohermaphroditism. Mutation detection at each of these candidate genes within the zebrafish cross identified hypomorphic variants on the female-associated allele of each locus. The two loci together accounted for 16% of variance of the trait. Interacting environmental cues are likely to be an additional important component of sex determination in zebrafish.