We propose an image encryption algorithm based on gradient decomposition and an improved logistic map. The original image is first decomposed into three subimages with different gradient sizes using the gradient decomposition. The pixel position of the three subimages is then changed by applying Arnold transformation, and the random sequence generated by the improved logistic map is used to perform the XOR operation on the three subimages. Subsequently, the row pixel values of the three subimages are converted into binary sequences, and then the binary sequences are shuffled with the random sequences generated by the improved logistic map. Finally, the three subimages are obtained as the R, G, and B components of the color image to generate the final encrypted image. For image decryption, the original image can be simply restored by joining the three subimages. The experimental results show that the improved logistic map has a larger key space and better randomness compared with the classical logistic map. Furthermore, the proposed encryption scheme exhibits better robustness against various attacks than several existing encryption algorithms.