Substitution boxes, or S-boxes, are critical elements of symmetric block cipher algorithms—these being the ones that provide “confusion” (a concept defined by Claude Shannon). This work presents a method for generating $8\times 8$ S-boxes using a multi-objective evolutionary algorithm, aiming to simultaneously optimize Nonlinearity (NL) and the Strict Avalanche Criterion (SAC), which are two important cryptographic properties of S-boxes. Chaotic maps were used to generate the initial population. Experimental executions were carried out, and the results were compared to evaluate the different Pareto fronts obtained. The results indicate that the proposed versions of our algorithm achieve good performance, comparable to the state of the art (with only 150 generations of execution), and it was also found that they continue to improve for runs of 5000 generations. This method can be used for the generation of S-boxes with specific properties.