The literature reported different chaotic-based image encryption algorithms. Three factors are used to evaluate performance of any encryption algorithm; computational complexity, security, and encryption speed. This paper proposes a novel chaotic map, referred to as Concave Chaotic Map (CCM), and investigates its characteristics. An image encryption algorithm is developed based on the CCM and used to encrypt grey-scale and plain-text images. Results indicate that the CCM achieves S-unimodality and provides chaotic behavior. Results also indicate that the proposed image encryption method provides acceptable encryption performance and high security.