The molecular identity and function of the Drosophila melanogaster Y-linked fertility factors have long eluded researchers. Although the D. melanogaster genome sequence was recently completed, the fertility factors still were not identified, in part because of low cloning efficiency of heterochromatic Y sequences. Here we report a method for iterative blast searching to assemble heterochromatic genes from shotgun assemblies, and we successfully identify kl-2 and kl-3 as 1beta- and gamma-dynein heavy chains, respectively. Our conclusions are supported by formal genetics with X-Y translocation lines. Reverse transcription-PCR was successful in linking together unmapped sequence fragments from the whole-genome shotgun assembly, although some sequences were missing altogether from the shotgun effort and had to be generated de novo. We also found a previously undescribed Y gene, polycystine-related (PRY). The closest paralogs of kl-2, kl-3, and PRY (and also of kl-5) are autosomal and not X-linked, suggesting that the evolution of the Drosophila Y chromosome has been driven by an accumulation of male-related genes arising de novo from the autosomes.