Although chaotic maps possess useful properties, such as being highly nonlinear and pseudorandom, for designing S-box, the cryptographic performance of the chaos-based substitution box (S-box) cannot achieve a very high level, especially in nonlinearity. In this paper, two conditions of improving the nonlinearity of S-box are firstly given according to the process of calculating nonlinearity. A novel method combining chaos and optimization operations is proposed for constructing S-box with high nonlinearity. There are three phases in our method. In the first phase, the S-box is initialized by a chaotic map. Then, its nonlinearity is enhanced by an optimization method in the second phase. To avoid the result of falling into local optima, some adjustments are done in the final phase. Experimental results show that the S-boxes constructed by the proposed method have a much higher nonlinearity than those only based on chaotic maps. This justifies that our algorithm is effective in generating S-boxes with high cryptographic performance.