We present two new approaches based on color histogram indexing for content-based retrieval of image databases. Since the high computational complexity has been one of the main barriers towards the use of similarity measures such as histogram intersection in large databases, we propose a hierarchical indexing scheme where computationally efficient features are used to subset the image before more sophisticated techniques are applied for precise retrieval. The use of histograms at different color resolutions as filtering and matching features in a hierarchical scheme is studied. In the second approach, a multiresolution representation of the histogram using the indices and signs of its largest wavelet coefficients is examined. Excellent results have been observed using the latter method.