In implementations of multi-resolution color-based image search, an image search system determines a color vector for a query image based on a color histogram of the query image by concatenating two color histograms having different resolutions. The image search system can compute distance measures between the color vector of the query image and color vectors of candidate images. The image search system can select one or more of the candidate images to return based on the distance measures utilizing the distance measures as indication of color similarity of the candidate images to the query image.