Color constancy is the ability to assign a constant color to an object independent of changes in illumination. Color constancy is achieved by taking context information into account. Previous approaches that have used matching paradigms to quantify color constancy found degrees of constancy between 20% and 80%. Here, we studied color constancy in a color-naming task under different conditions of surround illumination and patch size. Observers categorized more than 400 patches for each illumination condition. This allows one to overcome inherent limitations in color naming and to study the changes in color categories under illumination changes. When small central test patches with a full context illumination were categorized, observers followed the illumination shift almost completely, showing a high degree of constancy (99%). Reducing the available context information or increasing the patch size decreased the degree of constancy to about 50%. Moderate degrees of constancy (66%) occurred even when the test patches were never viewed simultaneously but only in temporal alternation with the illumination. Boundaries between color categories were largely stable within and across observers under neutral illumination. Under changing illumination, there were small but systematic variations in the color category boundaries. Color category boundaries tended to rotate away from the illumination color. This variation was largest under full context conditions where highest degrees of color constancy were obtained.