Combinatorial libraries offer an attractive approach towards exploring protein sequence, structure and function. Although several strategies introduce sequence diversity, the likelihood of identifying proteins with novel functions is increased when the library of genes encodes for folded and soluble structures. Here we present the first application of the binary patterning approach of combinatorial protein library design to the unique central linker region of the highly-conserved protein, calmodulin (CaM). We show that this high-quality approach translates very well to the CaM protein scaffold: all library members over-express and are functionally diverse, having a range of conformations in the presence and absence of calcium as determined by circular dichroism spectroscopy. Collectively, these data support that the binary patterning approach, when applied to the highly-conserved protein fold, can yield large collections of folded, soluble and highly-expressible proteins.