The tenth fibronectin type III (FN3) domain of human fibronectin (FNfn10), a prototype of the ubiquitous FN3 domain, is a small, monomeric beta-sandwich protein. In this study, we have bisected FNfn10 in each loop to generate a total of six fragment pairs. We found that fragment pairs bisected at multiple loops of FNfn10 show complementation in vivo as tested with a yeast two-hybrid system. The dissociation constant of these fragment pairs determined in vitro were as low as 3 nM, resulting in one of the tightest fragment complementation systems reported so far. Furthermore, we show that the affinity of fragment complementation is correlated with the stability of the uncut parent protein. Exploring this correlation, we screened a yeast two-hybrid library of one fragment and identified mutations that suppress the effect of a destabilizing mutation in the other fragment. One of the identified mutations significantly increased the stability of the uncut wild-type protein, proving that fragment complementation can be used as a novel strategy for the selection of proteins with enhanced stability.