Categorization researchers typically present single objects to be categorized. But real-world categorization often involves object recognition within complex scenes. It is unknown how the processes of categorization stand up to visual complexity or why they fail facing it. The authors filled this research gap by blending the categorization and visual-search paradigms into a visual-search and categorization task in which participants searched for members of target categories in complex displays. Participants have enormous difficulty in this task. Despite intensive and ongoing category training, they detect targets at near-chance levels unless displays are extremely simple or target categories extremely focused. These results, discussed from the perspectives of categorization and visual search, might illuminate societally important instances of visual search (e.g., diagnostic medical screening).