Extreme male dwarfism occurs in Osedax (Annelida: Siboglinidae), marine worms with sessile females that bore into submerged bones. Osedax are hypothesized to use environmental sex-determination (ESD), in which undifferentiated larvae that settle on bones develop as females, and subsequent larvae that settle on females transform into dwarf males. This study addresses several hypotheses regarding possible recruitment sources for the males: (1) common larval pool — males and females are sampled from a common pool of larvae; (2) neighborhood — males are supplied by a limited number of neighboring females; and (3) arrhenotoky — males are primarily the sons of host females. Osedax rubiplumus were sampled from submerged whalebones located at 1820 and 2893 m depths in Monterey Bay, California. Immature females typically did not host males, but mature females maintained male "harems" that grew exponentially in the number of males as female size increased. Allozyme analysis of the females revealed binomial proportions of nuclear genotypes, an indication of random sexual mating. Analysis of mitochondrial DNA sequences from the male harems and their host females allowed us to reject the arrhenotoky and neighborhood hypotheses for male recruitment. No significant partitioning of mitochondrial diversity existed between the male and female sexes, or between subsamples of worms collected at different depths or during different years (2002–2007). Mitochondrial sequence diversity was very high in these worms, suggesting that as many as 106 females contributed to a common larval pool from which the two sexes were randomly drawn.