Over the current decade, rapid growth in secured multimedia data communication has been observed due to the revolutionary upgrading of modern communication technology. Image encryption plays the most important role in providing confidentiality in secured image transmission over the network or for storage purposes. The (n, k) non-linear feedback shift register(NLFSR) and two chaotic maps, namely the Tanh Modulo Map and Self Parameterized Tent (SPT) Map, have been employed in combination with a key-dependent S-box to implement an image encryption scheme. A wide range of aperiodic sequences obtained from the NLFSR is initially used for image permutation. Afterward, the key-sensitive S-Box is included in the image substitution process. In the final phase, the Tanh Modulo Map and SPT Map-based expanded key stream are applied in image encryption. The scheme’s performance has been thoroughly examined using various relevant key factors, including histogram, correlation, entropy, and resistance to differential attacks. In addition, the stochastic behavior of the expanded key has been validated by the NIST SP800-22 test suite. Compared to closely related schemes by Allawi et al. [5, 8], the proposed scheme shows an average improvement of 75% and 48%, respectively, in the correlation analysis of encrypted images.