Evolutionary fitness threats and rewards are associated with subjectively unpleasant and pleasant sensations, respectively. Initially, these correlations appear explainable via adaptation by natural selection. But here I analyse the major metaphysical perspectives on consciousness – physicalism, dualism, and panpsychism – and conclude that none help to understand the adaptive-seeming correlations via adaptation. I also argue that a recently proposed explanation, the phenomenal powers view, has major problems that mean it cannot explain the adaptive-seeming correlations via adaptation either. So the mystery (...) – call it the evolutionary paradox of consciousness – remains. Some have used this mystery to argue for non-naturalistic (e.g. theistic) explanations. But I propose a naturalistic, non-adaptive explanation of the adaptive-seeming correlations: namely, ‘sensational associative learning’ during development. In this perspective, pairing of particular sensations with unconditioned stimuli – fitness rewards or threats – cause the sensations themselves to come to be interpreted as good or bad, respectively. Sensations, like colours, that are not reliably paired with either fitness rewards or threats remain largely unvalenced. Sensational associative learning also provides explanations for adaptive-seeming structural aspects of sensations, such as the observation that sounds of different pitch are experienced as ordinal in correspondence to their wavelengths while the same is not true of colours of different hue. The sensational associative learning perspective appears compatible with physicalism, panpsychism, and dualism (though not epiphenomenalism). (shrink)