Human observers can determine whether natural scenes contain an animal or not on the basis of as little as 20 ms viewing; a phenomenon termed ultra-rapid categorization (URC). Recent studies have suggested that URC is unimpaired even when attention resources are concurrently devoted to a second task. This apparent independence of URC from availability of attention resources presents a challenge for the conventional view of high-level vision as attention-demanding. However, one notable feature of the scenes employed in those experiments is that they almost universally comprised only one or two foreground objects. Here, we investigate whether these findings generalize to more complex scenes, more typical of those in nature. We find that categorization of scenes with four primary foreground objects is greatly impaired when attention resources are limited under dual-task conditions, even when scenes are presented for 500 ms. In contrast, URC of scenes with one foreground object is only mildly impaired—the magnitude of this impairment being equivalent to that observed for single objects presented in isolation without naturalistic scene backgrounds. We conclude that URC of complex scenes is particularly attention-dependent but that some attention resources are probably necessary even for URC of simple one-object scenes.