Categorical search involves looking for objects based on category information from long-term memory. Previous research has shown that search efficiency in categorical search is influenced by target/distractor similarity and category variability (i.e., heterogeneity). However, the interaction between these factors and their impact on different subprocesses of search remains unclear. This study examined the effects of target/distractor similarity and category variability on processes of categorical search. Using multidimensional scaling, we manipulated target/distractor similarity and measured category variability for target categories that participants searched for. Eye-tracking data were collected to examine attentional guidance and target verification. The results demonstrated that the effect of category variability on response times (RTs) was dependent on the level of target/distractor similarity. Specifically, when distractors were highly similar to target categories, there was a negative relation between RTs and variability, with low variability categories producing longer RTs than higher variability categories. Surprisingly, this trend was only present in the eye-tracking measures of target verification but not attentional guidance. Our results suggest that searchers more effectively guide attention to low-variability categories compared to high-variability categories, regardless of the degree of similarity between targets and distractors. However, low category variability interferes with target match decisions when distractors are highly similar to the category, thus the advantage that low category variability provides to searchers is not equal across processes of search.