In this paper, we propose a novel image encryption algorithm based on chaotic maps and least squares approximations. The proposed algorithm consists of two main phases, which are applied sequentially in several rounds, namely a shuffling phase and a masking phase. Both phases are based on 1–dimensional piecewise linear chaotic maps and act on the rows/columns of the input plain image. Least squares approximations are used to strengthen the security of the proposed algorithm by providing strong mixing between the rows/columns of the image. Simulation results show that the proposed image encryption algorithm is robust against common statistical and security attacks. We present thorough comparison of the proposed algorithm with some existing image encryption algorithms.