Small cystine-stabilized proteins are desirable scaffolds for therapeutics and diagnostics. Specific folding and binding properties of the proteinaceous binders can be engineered with combinatorial protein libraries in connection with artificial molecular evolution. The combinatorial protein libraries are composed of scaffold variants with random sequence variation, which inevitably produces a portion of the library sequences incompatible with the parent structure. Here, we used artificial molecular evolution to elucidate structure-determining residues in a smallest cystine-stabilized scaffold. The structural determinant information was then applied to designing cystine-stabilized miniproteins binding to human vascular endothelial growth factor. This work demonstrated a general methodology on engineering artificial cystine-stabilized proteins as antibody mimetics with simultaneously enhanced folding and binding properties.