The efficient coding hypothesis predicts that sensory neurons adjust their coding resources to optimally represent the stimulus statistics of their environment. To test this prediction in the moth olfactory system, we have developed a stimulation protocol that mimics the natural temporal structure within a turbulent pheromone plume. We report that responses of antennal olfactory receptor neurons to pheromone encounters follow the temporal fluctuations in such a way that the most frequent stimulus timescales are encoded with maximum accuracy. We also observe that the average coding precision of the neurons adjusted to the stimulus-timescale statistics at a given distance from the pheromone source is higher than if the same encoding model is applied at a shorter, non-matching, distance. Finally, the coding accuracy profile and the stimulus-timescale distribution are related in the manner predicted by the information theory for the many-to-one convergence scenario of the moth peripheral sensory system.