A novel color image encryption algorithm based on a cross 2D hyperchaotic map is proposed in this paper. The cross 2D hyperchaotic map is constructed using one nonlinear function and two chaotic maps with cross structure. Chaotic behaviors are illustrated using bifurcation diagrams, Lyapunov exponent spectra and phase portraits, etc. In the color image encryption algorithm, the keys are generated using hash function SHA-512 and the information of plain color image. First, the color plain image is converted to a combined bit-level matrix and permuted by the chaos based row and column combined cycle shift scrambling method. Then the scrambled integer matrix is diffused according to the selecting sequence which depends on the chaotic sequence. Last, the cipher color image is obtained by decomposed the diffused matrix. Simulation results show that the algorithm can encrypt the color image effectively and has good security.