The study of visual memory has repeatedly shown qualitatively similar visual short-term memory (VSTM) systems between human and many nonhuman species. In studies of human VSTM using change detection, increasing visual object complexity has an inverse effect on accuracy. In the current study, we assessed the functional relationship between visual object complexity and memory performance in visual change detection in pigeons and humans. Visual object complexity was quantified for each object type within each species using visual target search. Change detection performance was inversely related to object complexity in both species, suggesting that pigeon VSTM, like human VSTM, is limited by visual object complexity. Human participants were able to use a verbal-labeling strategy to mitigate some of the effect of visual object complexity, suggesting a qualitative difference in how the two species may solve certain visual discriminations. Considering the visual complexity of novel objects may also help explain previous failures to transfer relational rules to novel visual objects. © 2012 Elsevier B.V.