English and Russian color terms divide the color spectrum differently. Unlike English, Russian makes an obligatory distinction between lighter blues ("goluboy") and darker blues ("siniy"). We investigated whether this linguistic difference leads to differences in color discrimination. We tested English and Russian speakers in a speeded color discrimination task using blue stimuli that spanned the siniy/goluboy border. We found that Russian speakers were faster to discriminate two colors when they fell into different linguistic categories in Russian (one siniy and the other goluboy) than when they were from the same linguistic category (both siniy or both goluboy). Moreover, this category advantage was eliminated by a verbal, but not a spatial, dual task. These effects were stronger for difficult discriminations (i.e., when the colors were perceptually close) than for easy discriminations (i.e., when the colors were further apart). English speakers tested on the identical stimuli did not show a category advantage in any of the conditions. These results demonstrate that (i) categories in language affect performance on simple perceptual color tasks and (ii) the effect of language is online (and can be disrupted by verbal interference).