The current application describes various compositions and methods for the production of FN3-based binding proteins with improved stability properties. Aspects of the disclosure relate to polypeptides comprising a variant fibronectin type III (FN3) domain from Sulfolobus tokodaii or Pyrococcus horikoshii comprising one or more amino acid substitutions or insertions in a loop region of FN3, in a non-loop region of FN3, or in both.