By using the methods of random amplified polymorphic DNA (RAPD) and bulked segregate analysis (BSA), we identified markers that are linked to the sex determination in the dioecious Populus tomentosa. Male and female bulks were created through rough mixing equal amounts of its five individual DNA. A total of 88 primers were screened. Twelve primers produced clear patterns with at least one band that appeared to be polymorphic between the two bulks. Subsequently, five male and female individuals were analyzed with those 12 primers, and only S60 (ACCCGGTCAC) could generate a common 1800 bp DNA fragment in all five male individuals and male pool but not in any female individuals. It can be concluded that the gender of P. tomentosa is most likely connected to the S60–1800 bp DNA fragment and RAPD markers. S60, therefore, can be used for selecting the gender of P. tomentosa.