Genetic linkage maps are critical for assembling draft genomes to a meaningful chromosome level and for deciphering the genomic underpinnings of biological traits. The estimates of recombination rates derived from genetic maps also play an important role in understanding multiple aspects of genomic evolution such as nucleotide substitution patterns and accumulation of deleterious mutations. In this study, we developed a high-throughput experimental approach that combines fluorescence-activated cell sorting, whole-genome amplification, and short-read sequencing to construct a genetic map using single-sperm cells. Furthermore, a computational algorithm was developed to analyze single-sperm whole-genome sequencing data for map construction. These methods allowed us to rapidly build a male-specific genetic map for the freshwater microcrustacean Daphnia pulex, which shows significant improvements compared to a previous map. With a total of mapped 1672 haplotype blocks and an average intermarker distance of 0.87 cM, this map spans a total genetic distance of 1451 Kosambi cM and comprises 90% of the resolved regions in the current Daphnia reference assembly. The map also reveals the mistaken mapping of seven scaffolds in the reference assembly onto chromosome II by a previous microsatellite map based on F2 crosses. Our approach can be easily applied to many other organisms and holds great promise for unveiling the intragenomic and intraspecific variation in the recombination rates.