Individuals in groups, whether composed of humans or other animal species, often make important decisions collectively, including avoiding predators, selecting a direction in which to migrate and electing political leaders. Theoretical and empirical work suggests that collective decisions can be more accurate than individual decisions, a phenomenon known as the ‘wisdom of crowds’. In these previous studies, it has been assumed that individuals make independent estimates based on a single environmental cue. In the real world, however, most cues exhibit some spatial and temporal correlation, and consequently, the sensory information that near neighbours detect will also be, to some degree, correlated. Furthermore, it may be rare for an environment to contain only a single informative cue, with multiple cues being the norm. We demonstrate, using two simple models, that taking this natural complexity into account considerably alters the relationship between group size and decision-making accuracy. In only a minority of environments do we observe the typical wisdom of crowds phenomenon (whereby collective accuracy increases monotonically with group size). When the wisdom of crowds is not observed, we find that a finite, and often small, group size maximizes decision accuracy. We reveal that, counterintuitively, it is the noise inherent in these small groups that enhances their accuracy, allowing individuals in such groups to avoid the detrimental effects of correlated information while exploiting the benefits of collective decision-making. Our results demonstrate that the conventional view of the wisdom of crowds may not be informative in complex and realistic environments, and that being in small groups can maximize decision accuracy across many contexts.