Practical and technological applications of proteins are often limited by their low stability. Recent experimental and theoretical work suggests that large stability enhancements might be obtained through the design of the surface-charge distribution. However, for a typical protein, the number of different surface-charge distributions is huge, and an exhaustive search for the stabilizing distributions is clearly out of the question. We describe here a simple genetic algorithm that can search the space of the surface-charge distributions efficiently and can find many potentially stabilizing distributions under specified restrictions (such as, for instance, the fact that the active-site region is not modified or that the number of differences with the wild-type form is kept low). Also, the genetic algorithm could be employed to select small sets of interacting sites to be used in in vitro-directed evolution procedures that address the attainment of protein variants of enhanced stability.