Everyday dealing with enormous amounts of sensitive data requires its protection and communication over the insecure network. The field of ‘Steganography’ always attracted researchers for significant amount of scientific attention to protect and communicate sensitive data. This paper presents a secure steganography scheme for hiding Gray-scale secret image into a Color cover image by replacing cover image bits in frequency domain using modified quantum substitution box (S-Box). The inclusion of modified quantum S-Box for concealing secret bits in randomly selected any of the two channels of cover image ensures enhanced security. In the proposed scheme, we first performed discrete cosine transform (DCT) on the cover image. Then, quantum S-box is applied to locate the position of DCT coefficients where least significant bits are substituted intelligently based on the relative ordering of DCT frequencies. This relative ordering is achieved by traversing DCT coefficients in a zigzag manner where less important pixels have been altered more effectively without any major loss in image quality. The security of proposed method is examined by key space, key sensitivity parameters and robustness analysis. Additionally, the conducted simulation results demonstrate that our proposed steganography scheme has better visual image quality in terms of MSE, PSNR, UQI, SSIM, RMSE parameters as compared to other state-of-the-art works.