A new encryption scheme using dynamical 8 × 8 S-box, based on the composition of chaotic maps, is proposed. In this method, the dynamical S-box, one first uses a known chaotic dynamical system to generate a sequence of pseudo-random bytes, then applies certain permutations to them, using the discretized version of another two dimensional chaotic map. A sequence of pseudo-random bytes generated from two dimensional cat map is used to index the entry of the S-box. The output 8 bits (0-255) of the S-box are XOR-ed with the plaintext to obtain the ciphertext and XOR-ed with the ciphertext to obtain the plaintext. Standard statistical tests of this scheme are performed. We show that this new scheme can generate usable pseudo-random numbers, while maintaining a large enough keyspace for potential use in encryptions.