A new approach to retrieving images from a color image database is proposed in this paper. Each image in the database is represented by a pseudo two-dimensional hidden Markov model (2D PHMM), where both the chromatic and spatial information about the image could be adequately involved. In addition, a pictorial querying method is used, by which the users can paint only rough contents of the desired images if their information concerning the desired images is not crisp. The use of the flexible querying mechanism and 2D PHMMs eliminates the drawbacks of utilizing textual descriptions to retrieve images. Furthermore, effective statistical matching between the query picture and each image in the database can be achieved. The probability of the query picture generated by each 2D PHMM is just considered as the matching score between the query and the corresponding image. The images which best satisfy the query can thus be retrieved. Promising experimental results show the feasibility and effectiveness of the proposed approach.