Prions are proteins that convert between structurally and functionally distinct states, one or more of which is transmissible. In yeast, this ability allows them to act as non-Mendelian elements of phenotypic inheritance. To further our understanding of prion biology, we conducted a bioinformatic proteome-wide survey for prionogenic proteins in S. cerevisiae, followed by experimental investigations of 100 prion candidates. We found an unexpected amino acid bias in aggregation-prone candidates and discovered that 19 of these could also form prions. At least one of these prion proteins, Mot3, produces a bona fide prion in its natural context that increases population-level phenotypic heterogeneity. The self-perpetuating states of these proteins present a vast source of heritable phenotypic variation that increases the adaptability of yeast populations to diverse environments.