Lectins with a beta-propeller fold bind glycans on the cell surface through multivalent binding sites and appropriate directionality. These proteins are formed by repeats of short domains, raising questions about evolutionary duplication. However, these repeats are difficult to detect in translated genomes and seldom correctly annotated in sequence databases. To address these issues, we defined the blade signature of the five types of beta-propellers using 3D-structural data. With these templates, we predicted 3,887 beta-propeller lectins in 1,889 species and organized this information in a searchable online database. The data reveal a widespread distribution of beta-propeller lectins across species. Prediction also emphasizes multiple architectures and led to the discovery of a beta-propeller assembly scenario. This was confirmed by producing and characterizing a predicted protein coded in the genome of Kordia zhangzhouensis. The crystal structure uncovers an intermediate in the evolution of beta-propeller assembly and demonstrates the power of our tools.