Stress-induced mutagenesis has been observed in multiple species of bacteria and yeast. It has been suggested that in asexual populations, a mutator allele that increases the mutation rate during stress can sweep to fixation with the beneficial mutations it generates. However, even asexual microbes can undergo horizontal gene transfer and rare recombination, which typically interfere with the spread of mutator alleles. Here we examine the effect of horizontal gene transfer on the evolutionary advantage of stress-induced mutator alleles. Our results demonstrate that stress-induced mutator alleles are favored by selection even in the presence of horizontal gene transfer, and more so when the mutator alleles also increase the horizontal gene transfer rate. We suggest that when regulated by stress, mutation and horizontal gene transfer can be complementary, rather than competing, adaptive strategies, and that stress-induced mutagenesis has important implications for evolutionary biology, ecology, and epidemiology, even in the presence of horizontal gene transfer and rare recombination.