The DNA shuffling technique has been used to generate libraries of evolved enzymes in thermostability. We have shuffled two thermostable cytidine deaminases (CDAs) from Bacillus caldolyticus DSM405 (T53) and B. stearothermophilus IFO12550 (T101). The shuffled CDA library (SH1067 and SH1077 from the first round and SH2426 and SH2429 from the second round) showed various patterns in thermostability. The CDAs of SH1067 and SH1077 were more thermostable than that of T53. SH2426 showed 150% increased halftime than that of T53 at $70^{circ}C$. The CDA of SH2429 showed about 200% decreased thermostability than that of T53 at $70^{circ}C$. A single amino acid residue replacement that presented between SH1077 and SH2429 contributed to dramatic changes in specific activity and thermostability. On SDS-PAGE, the purified CDA of SH1077 tetramerized, whereas that of SH2429 denatured and became almost monomeric at $80^{circ}C$. A simulated three-dimensional structure for the mutant CDA was used to interpret the mutational effect.