A visual test was conducted to find color ranges in which a replacement stone is aesthetically compatible. This study describes a color calibrated image chain processing, from acquisition to display, that was used to simulate stone replacements on a realistic image of monument. Then, a visual test protocol was designed to locate color thresholds that separate a perceptible from an imperceptible replaced stone. A case study has been performed on the Aigues-Mortes medieval city walls (South of France): Fifteen naive observers rated 2160 proposals of simulated stone replacements. The observer's answers (acceptance or rejection) were used to compute color thresholds along three colorimetric axes in a physiological and device-independent color space (LMS). The results show that color thresholds are not centered on the mean color of the monument. Furthermore, lighter colors are not accepted, though these appear in the original wall. These color thresholds constitute a set of quantitative criteria for aesthetically compatible stones. (c) 2012 Wiley Periodicals, Inc. Col Res Appl, 38, 356-363, 2012