The significance of data security has become more critical due to the ever-changing goals and capabilities of attackers. As a result, many cryptosystems employing diverse approaches are being developed to safeguard sensitive data. A Substitution box (S-box) plays a vigorous role in modern cryptosystems because of its credence for inducing confusion during the encryption process and ultimately protecting the data. Currently, chaotic maps are being developed and widely employed to yield S-Boxes as the use of chaotic maps aids in the randomness and resistance to mitigate many cryptanalytic attacks. In this paper, a novel chaotic map and an inventive systematic search method are proposed for the generation of key-dependent dynamic and highly nonlinear S-boxes. A variety of standard cryptographic tests such as fixed-point analysis, nonlinearity (NL), strict avalanche criterion (SAC), bit independence criterion (BIC), linear probability (LP), differential probability (DP), etc.) are applied to assess and analyze the cryptographic strengths of S-boxes generated using the proposed method. The findings from experimental and comparative analyses show that the proposed S-box provides stronger and better cryptographic features (no fixed point, no opposite fixed point, average NL = 111.75, SAC offset = 0.0000, BIC-NL = 103.9, LP = 0.125, and DP = 0.039) than many of the existing S-boxes studies presented in recent years. Hence, the proposed S-box construction technique has a lot of potential and genuine prospects for its utilization in cryptographic applications to protect sensitive data from attackers.