The Clostridium thermocellum cellobiose phosphorylase (CtCBP) is a large protein consisting of 812 amino acids and has great potential in the production of sugar phosphates, novel glycosides, and biofuels. It is relatively stable at 50 °C, but is rapidly inactivated at 70 °C. To stabilize CtCBP at elevated temperatures, two protein-engineering approaches were applied, i.e. site-directed mutagenesis based on structure-guided homology analysis and random mutagenesis at various mutation rates. The former chose substitutions by comparison of the protein sequences of CBP homologs, utilized structural information to identify key amino acid residues responsible for enhanced stability, and then created a few variants accurately. The latter constructed large libraries of random mutants at different mutagenesis frequencies. A novel combinational selection/screening strategy was employed to quickly isolate thermostability-enhanced and active variants. Several stability-enhanced mutants were obtained by both methods. Manually combining the stabilizing mutations identified from both rational and random approaches led to the best mutant (CM3) with the halftime of inactivation at 70 °C extended from 8.3 to 24.6 min. The temperature optimum of CM3 was increased from 60 to 80 °C. These results suggested that a combination of rational design and random mutagenesis could have a solid basis for engineering large proteins.