Molecular evolution has focused on the divergence of molecular functions, yet we know little about how structurally distinct protein folds emerge de novo. We characterized the evolutionary trajectories and selection forces underlying emergence of β-propeller proteins, a globular and symmetric fold group with diverse functions. The identification of short propeller-like motifs (<50 amino acids) in natural genomes indicated that they expanded via tandem duplications to form extant propellers. We phylogenetically reconstructed 47-residue ancestral motifs that form five-bladed lectin propellers via oligomeric assembly. We demonstrate a functional trajectory of tandem duplications of these motifs leading to monomeric lectins. Foldability, i.e., higher efficiency of folding, was the main parameter leading to improved functionality along the entire evolutionary trajectory. However, folding constraints changed along the trajectory: initially, conflicts between monomer folding and oligomer assembly dominated, whereas subsequently, upon tandem duplication, tradeoffs between monomer stability and foldability took precedence. Display omitted •Inferred 47-aminoacid ancestral motifs fold into functional β-propeller assemblies•Motif duplication, fusion, and diversification yield functional monomeric propellers•Folding efficiency was the key parameter optimized throughout propeller emergence•Single-motif precursors in extant genomes support the reconstructed emergence pathway Experimental reconstruction of the emergence of a de novo protein indicates that “foldability” is the primary factor required for improved functionality along the entire evolutionary trajectory, although the parameters dictating optimal folding shifted as protein complexity increased.