Substitution box (S-box) is a critical part of the data encryption and decryption procedures. The primary function of the S-box in advanced encryption standard algorithm is to randomize the 8-bit input into 8-bit output. This paper presents a novel approach to S-box construction based on the replacement of irreducible polynomial and affine mapping. The strength of the created S-box is assessed by applying several standard tests, e.g., balance, bijective, nonlinearity, strict avalanche criterion, and bit independence criterion-nonlinearity. The strength of the S-box outperforms those of available S-boxes.