Males from different populations of the same species often differ in their sexually selected traits. Variation in sexually selected traits can be attributed to sexual selection if phenotypic divergence matches the direction of sexual selection gradients among populations. However, phenotypic divergence of sexually selected traits may also be influenced by other factors, such as natural selection and genetic constraints. Here, we document differences in male sexual traits among six introduced Australian populations of guppies and untangle the forces driving divergence in these sexually selected traits. Using an experimental approach, we found that male size, area of orange coloration, number of sperm per ejaculate and linear sexual selection gradients for male traits differed among populations. Within populations, a large mismatch between the direction of selection and male traits suggests that constraints may be important in preventing male traits from evolving in the direction of selection. Among populations, however, variation in sexual selection explained more than half of the differences in trait variation, suggesting that, despite within-population constraints, sexual selection has contributed to population divergence of male traits. Differences in sexual traits were also associated with predation risk and neutral genetic distance. Our study highlights the importance of sexual selection in trait divergence in introduced populations, despite the presence of constraining factors such as predation risk and evolutionary history.