Coevolutionary interactions between plants and their bacterial and eukaryotic pathogens are mediated by virulence effectors. These effectors face the daunting challenge of carrying out virulence functions, while also potentially exposing the pathogen to host defense systems. Very strong selective pressures are imposed by these competing roles, and the subsequent genetic changes leave their footprints in the extant allelic variation. This review examines the evolutionary processes that drive pathogen-host interactions as revealed by the genetic signatures left in virulence effectors, and speculate on the different pressures imposed on bacterial versus eukaryotic pathogens. We find numerous instances of positive selection for new allelic forms, and diversifying selection for genetic variability, which results in altered host-pathogen interactions. We also describe how the genetic structure of both bacterial and eukaryotic virulence effectors may contribute to their rapid generation and turnover.