The structural properties of proteins recovered from random sequence libraries can be used to investigate the relationship between folding and sequence information. Here, we show that helical proteins displaying cooperative thermal denaturation transitions can be easily recovered from a library containing 80-residue proteins predominantly composed of glutamine, leucine, and arginine, with an average hydrophobicity level similar to that of natural proteins. The native structure of one of these proteins has a stability and oligomeric form similar to that of many natural proteins but differs in having no slowly exchanging amide hydrogens.