Substitution Boxes (S-Boxes) play an important role in many modern-day cryptographic algorithms, more commonly known as ciphers. Without carefully chosen S-Boxes, such ciphers would be easier to break. Therefore, it is not surprising that the design of suitable S-Boxes attracts a lot of attention in the cryptography community. The evolutionary computation (EC) community also had several attempts using evolutionary paradigms to evolve S-Boxes with good cryptographic properties. This article focuses on a fitness function one should use when evolving highly nonlinear S-Boxes. After an extensive experimental analysis of the current state-of-the-art fitness functions, we present a new one that offers higher speed and better results when compared with the aforementioned fitness functions.