In this paper, we will show how non-photorealistic rendering (NPR) can take a new role in content-based image retrieval (CBIR). The proposed CBIR method applies a novel image similarity measure: Unlike traditional features like color, texture, or shape, our measure is based on a painted representation of the original image. This is produced by a stochastic paintbrush algorithm which simulates a painting process. We use the stroke parameters (color, size, orientation, and location) as features and similarity is measured by matching strokes of a pair of images. The advantage of our approach is that it provides information not only about the color content but also about the structural properties of an image without the segmentation of the image. Experimental results show that the CBIR method using paintbrush features has higher retrieval rate than traditional methods using color or texture features only.