Among the seven tetraploid cotton species, little is known about transmission genetics and genome organization in Gossypium mustelinum, the species most distant from the source of most cultivated cotton, G. hirsutum. In this research, an F2 population was developed from an interspecific cross between G. hirsutum and G. mustelinum (HM). A genetic linkage map was constructed mainly using simple sequence repeat (SSRs) and restriction fragment length polymorphism (RFLP) DNA markers. The arrangements of most genetic loci along the HM chromosomes were identical to those of other tetraploid cotton species. However, both major and minor structural rearrangements were also observed, for which we propose a parsimony-based model for structural divergence of tetraploid cottons from common ancestors. Sequences of mapped markers were used for alignment with the 26 scaffolds of the G. hirsutum draft genome, and showed high consistency. Quantitative trait locus (QTL) mapping of fiber elongation in advanced backcross populations derived from the same parents demonstrated the value of the HM map. The HM map will serve as a valuable resource for QTL mapping and introgression of G. mustelinum alleles into G. hirsutum, and help clarify evolutionary relationships between the tetraploid cotton genomes.