We have investigated the evolvability of an insoluble random polypeptide, RP3-34, to a soluble form through iterative mutation and selection with the aid of the green fluorescent protein (GFP) folding reporter. To assess the solubility of the polypeptides in the selected clones of each generation, the polypeptide genes were detached from the GFP fusions and expressed with a His(6) tag. The solubility of the variant random polypeptides increased in each generation within the scope of the evolutionary process, and the polypeptides assumed a soluble form from the fourth generation. Analysis of the synonymous and nonsynonymous mutations found in the deduced amino acid sequence of the selected polypeptides revealed that selection had accelerated the evolutionary rate. The solubility and hydrophobicity of the polypeptides and the 25 arbitrarily chosen random polypeptides found in a previously prepared library were determined, analyzed, and interpreted from the landscape on the protein sequence space. This study showed the evolvability of an insoluble arbitrary sequence toward a soluble one, hence, it provides a new perspective on the field of artificial evolution.