Survival of marine fishes exposed to elevated near-future CO2 levels is threatened by their altered responses to sensory cues. Here we demonstrate a novel physiological and molecular mechanism based in the olfactory system which helps explain altered behavior under elevated CO2. We combine electrophysiology and high throughput sequencing with behavioral experiments to investigate how elevated CO2 affects the olfactory system of European sea bass (Dicentrarchus labrax), an economically important species. Under elevated CO2 (~1000 μatm) fish need to be up to 42% closer to an odor source for detection, compared with current CO2 levels (~400 μatm), decreasing their chances of detecting food or predators. These findings correlated with a suppression in the transcription of genes involved in synaptic strength, cell excitability, and wiring of the olfactory system in response to sustained exposure to elevated CO2. Our results contrast with, but complement, the previously proposed mechanism of impaired neurotransmitter (γ-aminobutyric acid) function, and demonstrate that both the olfactory system and central brain function are compromised by elevated CO2 in the oceans, with potentially major negative impacts on fish globally.