Single-molecule imaging analysis of chemotactic response in eukaryotic cells has revealed a stochastic nature in the input signals and the signal transduction processes. This leads to a fundamental question about the signaling processes: how does the signaling system operate under stochastic fluctuations or noise? Here, we report a stochastic model of chemotactic signaling in which noise and signal propagation along the transmembrane signaling pathway by chemoattractant receptors can be analyzed quantitatively. The results obtained from this analysis reveal that the second-messenger-production reactions by the receptors generate noisy signals that contain intrinsic noise inherently generated at this reaction and extrinsic noise propagated from the ligand-receptor binding. Such intrinsic and extrinsic noise limits the directional sensing ability of chemotactic cells, which may explain the dependence of chemotactic accuracy on chemical gradients that has been observed experimentally. Our analysis also reveals regulatory mechanisms for signal improvement in the stochastically operating signaling system by analyzing how the SNR of chemotactic signals can be improved on or deteriorated by the stochastic properties of receptors and second-messenger molecules. Theoretical consideration of noisy signal transduction by chemotactic signaling systems can further be applied to signaling systems in general.