Genetic improvement in yield and fiber quality is needed for worldwide cotton production. Identification of molecular markers associated with fiber-related traits can facilitate selection for these traits in breeding. This study was designed to identify associations between SSR markers and fiber traits using an exotic germplasm population, species polycross (SP), derived from multiple crosses among Gossypium tetraploid species. The SP population underwent 11 generations of mixed random mating and selfing followed by 12 generations of selfing. A total of 260 lines were evaluated for fiber-related traits under three environments in 2005 and 2006. Large genotypic variance components in traits were identified relative to components of genotype x environment. Eighty-six primer pairs amplified a total of 314 polymorphic fragments among 260 lines. A total of 202 fragments with above 6% allele frequency were analyzed for associations. Fifty-nine markers were found to have a significant (P < 0.05, 0.01, or 0.001) association with six fiber traits. There were six groups identified within the population using structure analysis. Allele frequency divergence among six groups ranged from 0.11 to 0.27. Of the 59 marker-trait associations, 39 remained significant after correction for population structure and kinship using a mixed linear model. The effect of population sub-structure on associations was most significant in boll weight among the traits analyzed. The sub-structure among the SP lines may be caused by natural selection, the breeding method applied during development of inbred lines, and unknown factors. The identified marker-trait associations can be useful in breeding and help determine genetic mechanisms underlying interrelationships among fiber traits.