Environmental shifts and lifestyle changes may result in formerly adaptive traits becoming non-functional or maladaptive. The subsequent decay of such traits highlights the importance of natural selection for adaptations, yet its causes have rarely been investigated. To study the fate of formerly adaptive traits after lifestyle changes, we evaluated sexual traits in five independently derived asexual lineages, including traits that are specific to males and therefore not exposed to selection. At least four of the asexual lineages retained the capacity to produce males that display normal courtship behaviours and are able to fertilize eggs of females from related sexual species. The maintenance of male traits may stem from pleiotropy, or from these traits only regressing via drift, which may require millions of years to generate phenotypic effects. By contrast, we found parallel decay of sexual traits in females. Asexual females produced altered airborne and contact signals, had modified sperm storage organs, and lost the ability to fertilize their eggs, impeding reversals to sexual reproduction. Female sexual traits were decayed even in recently derived asexuals, suggesting that trait changes following the evolution of asexuality, when they occur, proceed rapidly and are driven by selective processes rather than drift.