A procedure for optimizing basis sets for core hole binding energies is described. Contracted Gaussian basis sets are optimized for ground state and core hole state atomic configurations, exponents and contraction coefficients being determined by a minimization of the atomic self-consistent field state within a simulated annealing procedure. The basis sets are used in connection with Deltaself-consistent field, DeltaMoller-Plesset and DeltaKohn-Sham theory calculations of core electron binding energies and chemical shifts of high accuracy. Whatever the method, the small basis sets optimized in this way give results with an accuracy comparable to that obtained using very extended normal basis sets close to the complete basis set limit. They provide an excellent alternative to treat large molecular systems and push the accuracy of the DeltaKohn-Sham technique for binding energy computations even further, exhibiting only small (a few tenths of an electron volt) deviations from experimental data.