Cyclic peptides binding to targets of interest can be generated efficiently with powerful in vitro display techniques, such as phage display or mRNA display. The cyclic peptide libraries screened with these methods are generated by altering in a combinatorial fashion the amino acid sequence of the peptides, the number of amino acids in the macrocycle rings, and the cyclization chemistry. A structural element that cannot easily be varied in the cyclic peptides is the backbone, which is built from amino acids, each of which contributes three atoms to the macrocyclic ring structure. Here, we proposed to improve the affinity of a phage-selected bicyclic peptide inhibitor of coagulation factor XII (FXII) by screening variants with one or two carbon atoms inserted into different positions of the backbone, and thus tapping into a structural space that was not sampled by phage display. Two mutants showed 4.7- and 2.5-fold improved K-i values. The better one blocked FXII with a Ki of 1.5 +/- 0.1 nm and inhibited activation of the intrinsic coagulation pathway (EC2x 1.7 mm). The strategy of ring size variation by one or several atoms should be generally applicable for the affinity maturation of in-vitro-evolved cyclic peptides.