Many cellular systems rely on the ability to interpret spatial heterogeneities in chemoattractant concentration to direct cell migration. The accuracy of this process is limited by stochastic fluctuations in the concentration of the external signal and in the internal signaling components. Here we use information theory to determine the optimal scheme to detect the location of an external chemoattractant source in the presence of noise. We compute the minimum amount of mutual information needed between the chemoattractant gradient and the internal signal to achieve a prespecified chemotactic accuracy. We show that more accurate chemotaxis requires greater mutual information. We also demonstrate that a priori information can improve chemotaxis efficiency. We compare the optimal signaling schemes with existing experimental measurements and models of eukaryotic gradient sensing. Remarkably, there is good quantitative agreement between the optimal response when no a priori assumption is made about the location of the existing source, and the observed experimental response of unpolarized Dictyostelium discoideum cells. In contrast, the measured response of polarized D. discoideum cells matches closely the optimal scheme, assuming prior knowledge of the external gradient-for example, through prolonged chemotaxis in a given direction. Our results demonstrate that different observed classes of responses in cells (polarized and unpolarized) are optimal under varying information assumptions.