Protein conformational stability is of fundamental importance in protein structure and function. Engineering protein stability is a challenge within the pharmaceutical and biotechnology industries, and current methods are generally limited to large screening methodologies or a priori knowledge of the protein structure.We investigated the use of a Markov chain algorithm for sequence based engineering of protein thermostability. The Markov method was compared against the previously established consensus method, and both were applied to the fibronectin type III (FN3) domain and a serine protease inhibitor (serpin). Experimental and computational results showed a marked increase in thermal stability of the consensus designed FN3 domain and the consensus designed serpin (conserpin), both having melting temperatures greater than 100℃. The engineered FN3 has the highest thermal stability reported to date. Analysis using X-ray crystallography, CD spectroscopy and molecular dynamics simulations provides detailed insights into the structural and dynamic characteristics underlying their improved stability.