An optimal solubility screen is described that uses the results of crystallization trials to identify buffers that improve protein solubility and, in turn, crystallization success. This screen is useful not only for standard crystallization experiments, but also can easily be implemented into any high-throughput structure-determination pipeline. As a proof of principle, the predicted novel-fold protein AF2059 from Archaeoglobus fulgidus, which was known to precipitate in most buffers and particularly during concentration experiments, was selected. Using the crystallization results of 192 independent crystallization trials, it was possible to identify a buffer containing 100 mM CHES pH 9.25 that significantly improves its solubility. After transferring AF2059 into this ;optimum-solubility' buffer, the protein was rescreened for crystal formation against these same 192 conditions. Instead of extensive precipitation, as observed initially, it was found that 24 separate conditions produced crystals and the exchange of AF2059 into CHES buffer significantly improved crystallization success. Fine-screen optimization of these conditions led to the production of a crystal suitable for high-resolution (2.2 A) structure determination.