Trichromatic color vision is a fundamental aspect of the visual system shared by humans and non-human primates. In human observers, color has been shown to facilitate object identification. However, little is known about the role that color plays in higher level vision of non-human primates. Here, we addressed this question and studied the interaction between luminance- and color-based structural information for the recognition of natural scenes. We present psychophysical data showing that both monkey and human observers equally profited from color when recognizing natural scenes, and they were equally impaired when scenes were manipulated using colored noise. This effect was most prominent for degraded image conditions. By using a specific procedure for stimulus degradation, we found that the improvement as well as the impairment in visual memory performance is due to contribution of image color independent of luminance-based object information. Our results demonstrate that humans as well as non-human primates exploit their sensory ability of color vision to achieve higher performance in visual recognition tasks especially when shape features are degraded.