Living cells depend upon the detection of chemical signals for their existence. Eukaryotic cells can sense a concentration difference as low as a few per cent across their bodies. This process was previously suggested to be limited by the receptor-ligand binding fluctuations. Here, we first determine the chemotaxis response of Dictyostelium cells to static folic acid gradients and show that they can significantly exceed this sensitivity, responding to gradients as shallow as 0.2% across the cell body. Second, using a previously developed information theory framework, we compare the total information gained about the gradient (based on the cell response) to its upper limit: the information gained at the receptor-ligand binding step. We find that the model originally applied to cAMP sensing fails as demonstrated by the violation of the data processing inequality, i.e. the total information exceeds the information at the receptor-ligand binding step. We propose an extended model with multiple known receptor types and with cells allowed to perform several independent measurements of receptor occupancy. This does not violate the data processing inequality and implies the receptor-ligand binding noise dominates both for low- and high-chemoattractant concentrations. We also speculate that the interplay between exploration and exploitation is used as a strategy for accurate sensing of otherwise unmeasurable levels of a chemoattractant. © 2013 The Author(s).