Both freezing tolerance and NaCl tolerance are improved when antifreeze proteins are expressed as fusion proteins with two domains of staphylococcal protein A (SPA) in Escherichia coli. To characterize these properties further we created a randomly mutated expression library in E. coli, based on the winter flounder antifreeze protein HPLC-8 component gene. Low-fidelity PCR products of this gene were fused to the spa gene encoding two domains of the SPA. The library was screened for enhanced NaCl tolerance and four clones were selected. The freezing tolerance of each of the selected clones was enhanced to varying extents. DNA sequencing of the isolated mutants revealed that the amphiphilic properties of the native antifreeze protein were essentially conserved. Furthermore, by studying the primary sequence of the randomly mutated clones, in comparison with the degree of freezing tolerance, we have identified clues which help in understanding the relationship between salt and freezing tolerance.