Color is a salient feature which conveys important information about the objects in our visual world and may help identification and recognition. Previous psychophysical experiments in humans suggest that color can be beneficial in visual memory tasks, when shape information is no longer available. Here, we ask whether color in natural scenes improves object recognition under conditions in which shape information is degraded. We used a procedure based on Fourier analysis to create natural scenes, for which we manipulated color and shape information independently. Psychophysical performance of human observers was measured in a delayed matching to sample paradigm. Our observers were presented with natural scenes that contained object related (color image), irrelevant (colored noise) or no color (achromatic image and noise) for which we parametrically varied shape information by introducing noise into the images. Subjects performed significantly better when images contained object related color than no or irrelevant color information across the different noise levels (N = 8, p<0.05). In addition, performance across subjects did not differ for the achromatic stimuli and the images including unrelated color. Our results suggest that recognition of natural scenes can be enhanced by color information that is related to the object.