Several recent studies show that previous experience can influence observers’ search strategy in a way that improves search performance. The purpose of the present study is to investigate how the experience of difficult color discriminability affects search strategies. Two participant groups either experienced difficult color discriminability in a half of the trials (i.e., hard-discrimination group) or experienced easy search in all trials (i.e., easy-discrimination group) in a dual-target search task. Participants were required to respond to the presence of a target (colored T) among distractors (colored pseudo-L). Eye movements were recorded to understand which feature information is used to guide attention, and behavioral performance was measured to compare search efficiency between the two groups. The hard-discrimination group fixated more distractors with target-dissimilar colors than the easy-discrimination group, suggesting the hard-discrimination group used shape information to guide search more than the easy-discrimination group. However, error rates and response times were not significantly different between groups. The results demonstrate that the experience of difficult color discriminability discourages observers from guiding attention by color, and encourages them to use shape information.