Two central features of leukocyte chemosensory movement behavior demand fundamental theoretical understanding. In uniform concentrations of chemoattractant, these cells exhibit a persistent random walk, with a characteristic "persistence time" between significant changes in direction. In chemoattractant concentration gradients, they demonstrate a biased random walk, with an "orientation bias" characterizing the fraction of cells moving up the gradient. A coherent picture of cell-movement responses to chemoattractant requires that both the persistence time and the orientation bias be explained within a unifying framework. In this paper we offer the possibility that "noise" in the cellular signal perception/response mechanism can simultaneously account for these two key phenomena. In particular, we report on a stochastic mathematical model for cell locomotion based on kinetic fluctuations in chemoattractant receptor binding. This model proves to be capable of simulating cell paths similar to those observed experimentally for two cell types examined to date: neutrophils and alveolar macrophages, under conditions of uniform chemoattractant concentrations as well as chemoattractant concentration gradients. Further, this model can quantitatively predict both cell persistence time and dependence of orientation bias on gradient size. The model also successfully predicts that an increase in persistence time is associated with a decrease in orientation for typical system parameter values, as is observed for alveolar macrophages in comparison to neutrophils. Thus, the concept of signal "noise" can quantitatively unify the major characteristics of leukocyte random motility and chemotaxis. The same level of noise large enough to account for the observed frequency of turning in uniform environments is simultaneously small enough to allow for the observed degree of directional bias in gradients. This suggest that chemosensory cell movement behavior may be based on a "usefully" imperfect integrated signal response system, which allows both random and directed searches under appropriate conditions.