In spatial domain image steganography, Least Significant Bits (LSB) of cover image pixels are used to embed a secret message due to minimal distortion and higher payload capacity. In this paper, we have introduced an exclusive-OR (XOR) based encoding of encrypted secret message bits using varying higher-order pixel intensity bits. Encoding and LSB embedding is done block-wise by dividing the cover image into a number of blocks. The secret message is first encrypted using symmetric key cryptography and then encoded those encrypted bits by XORing them with randomly selected higher-order pixel bis of the cover image to obscure the secret bits further. Next, an inversion technique is applied to the encoded bits block-wise to keep the LSB bit changes to a minimum. The stego-key consists of the symmetric encryption key and the encode-key containing parameter settings such as the number_of_blocks, starting_block, start_pixel_offset, block_selection_rule, etc. This stego-key is shared prior to the actual communication using public-key cryptography to ensure the key’s authenticity and integrity. The extraction process does not require the cover image; the stego-image and the stego-key are sufficient. Experimental results show the visual imperceptibility along with improved image quality metrics such as Mean Square Error (MSE), Peak Signal to Noise Ratio (PSNR), Normalized Cross-Correlation (NCC), and Structural Similarity (SSIM) index in comparison to other well-known techniques. The average PSNR value remains above 51dB, even with 90% of the capacity utilized. The proposed scheme successfully eludes many standard steganalysis attacks such as histogram-based analysis (PDH), chi-square based embed probability test, Regular and Singular groups (RS) analysis, sample pair test, etc. on the tested stego-images. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.