This work shows a new design of substitution box (S-Box) construction for the implementation in the block cipher. The S-Box is the only component in block cipher such as advanced encryption standard (AES) that possess the nonlinearity characteristics. Hence, it is crucial to properly design so that it able resist the cipher against known attack such as linear and differential attacks. Thee construction is based on composition of permutation within the symmetric group. This paper focus on the AES S-Box class which received 8-bit input and produced 8-bit output. This bijective S-Box consist of 256 elements which later involve in the process of composition. Initially, a set of 30 S-Box with high nonlinearity is generated using 30 irreducible polynomials under the finite field GF(28). These S-Box is then undergoing two rounds of composition which finally yield about 1.62 million S-Box. More than half of the generated S-Box achieve the nonlinearity of at least 100 with the maximum recorded nonlinearity of 110. This method also guarantee that the generated S-Box is bijective. To show the security level of our construction method, a comparison to other constriction methods is conducted. The methods introduced in this paper have slightly higher nonlinearity compared to several construction with the value of differential uniformity not on the par as AES however comparable to other similar heuristic construction.