This paper investigates a particular family of enhanced substitution boxes for the Advanced Encryption Standard. In contrast to the original substitution box design where each input has relatively short orbit lengths, the modified S-boxes proposed here have the maximal periodicity property. In the family of enhanced substitution boxes, every S-box input has the maximum orbit length, which is 256. We determine completely all the parameters for the S-box to have this maximal periodicity property. We also show that our new enhanced S-boxes have better bit avalanche property.