To examine whether a primordial functional protein at the early stages of evolution has structural features, we carried out experimental evolution consisting of 25 cycles (generations) of mutation and selection toward DNA-binding function using a random-sequence polypeptide of 139 amino acid residues with no secondary structure as the initial sequence. In each generation, 16 clones were sampled arbitrarily for sequence analysis, and a phylogenetic tree was constructed. Polypeptide evolution proceeded from the initial point on branch I in 2 main directions of branches II and III. The initial and 2 evolved polypeptides (one at the 24th generation on branch III and the other at the 25th generation on branch II) were purified to examine their functional and structural properties. Although binding of the initial polypeptide to the target DNA was not detected by surface plasmon resonance measurements, the 2 evolved polypeptides bound to the DNA with dissociation constants of 1.6 and 1.0 μM, respectively, indicating an increase in affinity during the experimental evolution. Circular dichroism spectra of the evolved polypeptides, but not of the initial polypeptide, showed features characteristic of the polyproline II (PPII)–like structure, a left-handed helical structure commonly found in natural proteins, suggesting that the structure emerged through the experimental evolution. The same structural feature was found in another experimental evolution toward catalytic activity. These results demonstrate that the PPII-like structure is one of the common features that could have appeared in the early evolutionary stages of primordial functional protein.