Content-based Image Retrieval (CBIR) techniques have been extensively studied with the rapid growth of digital images. Generally, CBIR service is quite expensive in computational and storage resources. Thus, it is a good choice to outsource CBIR service to the cloud server that is equipped with enormous recourses. However, the privacy protection becomes a big problem, as the cloud server cannot be fully trusted. In this paper, we propose an outsourced CBIR scheme based on a novel bag-of-encrypted-words (BOEW) model. The image is encrypted by color value substitution, block permutation, and intra-block pixel permutation. Then, the local histograms are calculated from the encrypted image blocks by the cloud server. All the local histograms are clustered together, and the cluster centers are used as the encrypted visual words. In this way, the bag-of-encrypted-words (BOEW) model is built to represent each image by a feature vector, i.e., a normalized histogram of the encrypted visual words. The similarity between images can be directly measured by the Manhattan distance between feature vectors on the cloud server side. Experimental results and security analysis on the proposed scheme demonstrate its search accuracy and security.