This paper proposes a new region-based image retrieval technique called Principal Regions Image Retrieval (PRIR). This technique starts by segmenting an image to the most general principal regions and applies a fuzzy feature histogram to describe the color and texture properties of each segmented region. The proposed approach starts by generating a nearest neighbor graph for the segmented regions, and applying a greedy graph matching algorithm with a modified scoring function to determine the image rank. The proposed segmentation approach provides significant speedup toward state of the art techniques while keeping accurate precision. Moreover, the proposed approach combines local and global description to improve the retrieval results. Standard image databases are used to evaluate the performance of the proposed system. Results show that the proposed approach enhances the accuracy of retrieval compared to other approaches reported in the literature.