In this paper, a new algorithm called Gabor wavelet correlogram (GWC) is proposed for image indexing and retrieval. GWC is an effort to extend our former wavelet correlogram algorithm by introducing rotation invariant features using Gabor wavelets. We also present some ideas in order to handle effectively the redundancy problem due to non-orthogonal decomposition of Gabor wavelets. Additionally, we use an optimized weighted relative distance measure to improve the retrieval performance. The retrieval results obtained by applying GWC to a 1000 image database demonstrated significant improvements in rank, precision, and recall compared to the wavelet correlogram and enhanced wavelet correlogram algorithms.