In this paper, a novel image encryption scheme is proposed based on combination of pixel shuffling and new modified version of simplified AES. Chaotic baker’s map is used for shuffling and improving S-AES efficiency through S-box design. Chaos is used to expand diffusion and confusion in the image. Due to sensitivity to initial conditions, chaotic baker’s map has a good potential for designing dynamic permutation map and S-box. In order to evaluate performance, the proposed algorithm was measured through a series of tests. These tests included visual test and histogram analysis, randomness test, information entropy, encryption quality, correlation analysis, differential analysis and sensitivity analysis. Experimental results show that the new cipher has satisfactory security and is more efficient than AES which makes it a potential candidate for encryption of multimedia data.