Objects and their spatial relationships are important features for human visual perception. In most existing content-based image retrieval systems, however, only global features extracted from the whole image are used. While they are easy to implement, they have limited power to model semantic-level objects and spatial relationship. To overcome this difficulty, this paper proposes a constraint-based region matching approach to image retrieval. Unlike existing region-based approaches where either individual regions are used or only first-order constraints are modeled, the proposed approach formulates the problem in a probabilistic framework and simultaneously models both first-order region properties and second-order spatial relationships for all the regions in the image. Specifically, in this paper we present a complete system that includes image segmentation, local feature extraction, first- and second-order constraints, and probabilistic regionweight estimation. Extensive experiments have been carried out on a large heterogeneous image collection with 17,000 images. The proposed approach achieves significantly better performance than the state-of-the-art approaches.