Protein stability arises from a combination of factors which are often difficult to rationalise. Therefore its improvement is better addressed through directed evolution than by rational design approaches. In this study, five rounds of mutagenesis/recombination followed by high-throughput screening (≈10,000 clones) yielded the hit 1B6 showing a 300-fold higher half life at 50°C than that exhibited by the homodimeric wild type PpAzoR azoreductase from Pseudomonas putida MET94. The characterization using fluorescence, calorimetry and light scattering shows that 1B6 has a folded state slightly less stable than the wild type (with lower melting and optimal temperatures) but in contrast is more resistant to irreversible denaturation. The superior kinetic stability of 1B6 variant was therefore related to an increased resistance of the unfolded monomers to aggregation through the introduction of mutations that disturbed hydrophobic patches and increased the surface net charge of the protein. Variants 2A1 and 2A1-Y179H with increased thermodynamic stability (10 to 20°C higher melting temperature than wild type) were also examined showing the distinctive nature of mutations that lead to improved structural robustness: these occur in residues that are mostly involved in strengthening the solvent-exposed loops or the inter-dimer interactions of the folded state.