Invasive species often exhibit rapid evolutionary changes, and can provide powerful insights into the selective forces shaping phenotypic traits that influence dispersal rates and/or sexual interactions. Invasions also may modify sexual dimorphism. We measured relative lengths of forelimbs and hindlimbs of more than 3000 field-caught adult cane toads ( Rhinella marina ) from 67 sites in Hawai'i and Australia (1–80 years post-colonization), along with 489 captive-bred individuals from multiple Australian sites raised in a ‘common garden’ (to examine heritability and reduce environmental influences on morphology). As cane toads spread from east to west across Australia, the ancestral condition (long limbs, especially in males) was modified. Limb length relative to body size was first reduced (perhaps owing to natural selection on locomotor ability), but then increased again (perhaps owing to spatial sorting) in the invasion vanguard. In contrast, the sex disparity in relative limb length has progressively decreased during the toads' Australian invasion. Offspring reared in a common environment exhibited similar geographical divergences in morphology as did wild-caught animals, suggesting a genetic basis to the changes. Limb dimensions showed significant heritability (2–17%), consistent with the possibility of an evolved response. Cane toad populations thus have undergone a major shift in sexual dimorphism in relative limb lengths during their brief (81 years) spread through tropical Australia.