Understanding how neural populations encode natural stimuli with complex spatiotemporal structure to give rise to perception remains a central problem in neuroscience. Here we investigated population coding of natural communication stimuli by hindbrain neurons within the electrosensory system of weakly electric fish Apteronotus leptorhynchus. Overall, we found that simultaneously recorded neural activities were correlated: signal but not noise correlations were variable depending on the stimulus waveform as well as the distance between neurons. Combining the neural activities using an equal-weight sum gave rise to discrimination performance between different stimulus waveforms that was limited by redundancy introduced by noise correlations. However, using an evolutionary algorithm to assign different weights to individual neurons before combining their activities (i.e., a weighted sum) gave rise to increased discrimination performance by revealing synergistic interactions between neural activities. Our results thus demonstrate that correlations between the neural activities of hindbrain electrosensory neurons can enhance information about the structure of natural communication stimuli that allow for reliable discrimination between different waveforms by downstream brain areas.