The likelihood of genetic exchange among individuals is one of the most important known influences on evolutionary change—structuring both the level of genetic variation and the rate of evolution within populations. For the androdioecious model nematode, Caenorhabditis elegans, genetic exchange is only possible via outcrossing between males and hermaphrodites. C. elegans males, however, are thought to be rare, poor at mating, and potentially obsolete given that inbreeding depression is absent in this species. This is certainly true of the common lab strain N2 for which male frequency is notoriously low (0.001) and male mating ability is too poor to achieve higher frequencies under normal lab conditions. However, we have repeatedly observed that populations of C. elegans worms undergoing adaptation to novel environments maintain males at remarkably high frequencies. We also observe that male frequency increases in response to stress. Here we present the growing body of evidence that contrary to the prevailing view of C. elegans males as rare and inconsequential, C. elegans males play valuable roles in adaptation to novel environments and in response to stress. In independent experiments, C. elegans populations were adapted to one of three unique maintenance environments: 1) bleach/NaOH treatments in conjunction with new food and media conditions; 2) necessity to traverse “mountainous” terrain to obtain food; 3) exposure to the bacterial pathogen Serratia marcescens. In response, male frequencies are consistently both significantly and substantially elevated relative to control lines and/or ancestors with frequencies approaching 50% in some cases. Additionally, both male frequency and outcrossing rates increase following exposure to stress induced by overcrowding and starvation leading to dauer larva formation. These studies provide compelling evidence that the generally accepted view of C. elegans males as mere relicts or genetic mistakes is false. Rather, in line with our understanding of the importance of outcrossing in adaptation to novel environments, C. elegans males play a vital role that process.