Site-saturation mutagenesis is a powerful tool for protein optimization due to its efficiency and simplicity. A degenerate codon NNN or NNS (K) is often used to encode the 20 standard amino acids, but this will produce redundant codons and cause uneven distribution of amino acids in the constructed library. Here we present a novel "small-intelligent" strategy to construct mutagenesis libraries that have a minimal gene library size without inherent amino acid biases, stop codons, or rare codons of Escherichia coli by coupling well-designed combinatorial degenerate primers with suitable PCR-based mutagenesis methods. The designed primer mixture contains exactly one codon per amino acid and thus allows the construction of small-intelligent mutagenesis libraries with one gene per protein. In addition, the software tool DC-Analyzer was developed to assist in primer design according to the user-defined randomization scheme for library construction. This small-intelligent strategy was successfully applied to the randomization of halohydrin dehalogenases with one or two randomized sites. With the help of DC-Analyzer, the strategy was proven to be as simple as NNS randomization and could serve as a general tool to efficiently randomize target genes at positions of interest.