Steganography is the art of hiding confidential information (secret) within any media file (cover media) to produce an amalgamated secret-cover media called stego media, so that the secret cannot be recognized or recovered by unauthorized recipients. Many steganalysis techniques have been developed enabling recognition of the existence of secrets within stego media and recovering it. Therefore, it is necessary to develop more secure steganography algorithms. This paper presents a detailed description of a new secure Block Permutation Image Steganography (BPIS) algorithm. The algorithm converts the secret message to a binary sequence, divides the binary sequence into blocks, permutes the block using a key-based randomly generated permutation, concatenates the permuted blocks forming a permuted binary sequence, and then utilizes the Least-Significant-Bit (LSB) approach to embed the permuted binary sequence into BMP image file. The algorithm performance is investigated through performing a number of experiments, and for each experiment the PSNR (Peak Signal-to-Noise Ratio) between the stego and cover images is calculated. The results show that the algorithm provides high image quality, and invisibility, and most importantly higher security as secret cannot be recovered without knowing the permutation, which has a complexity of O(N!), where N is the length of the permutation.