Labels are indispensable visual (communication) elements that completely deliver the geospatial message of maps. The objective of this study is to investigate the impact of complementary colors between the map's background and text on the readability of cartographic texts and thus on the efficiency of the map user's search task. This is compared with the use of the traditional black labels on the corresponding colored backgrounds. Furthermore, a number of user characteristics, such as gender and expertise, are taken into account as well. The users' eye movements were registered to study their attentive behavior during the visual search task. In addition to the complement of the color's hue, the analyses were based on the difference in luminance, which could also affect the labels' readability. The difference between the black and colored label design was significantly different versus the eye-tracking metrics. A correlation was found between the color difference and reaction time measurement and between the luminance difference and fixation duration. (c) 2014 Wiley Periodicals, Inc. Col Res Appl, 40, 437-445, 2015