Directed cell motion in response to an external chemical gradient occurs in many biological phenomena such as wound healing, angiogenesis, and cancer metastasis. Chemotaxis is often characterized by the accuracy, persistence, and speed of cell motion, but whether any of these quantities is physically constrained by the others is poorly understood. Using a combination of theory, simulations, and 3D chemotaxis assays on single metastatic breast cancer cells, we investigate the links among these different aspects of chemotactic performance. In particular, we observe in both experiments and simulations that the chemotactic accuracy, but not the persistence or speed, increases with the gradient strength. We use a random walk model to explain this result and to propose that cells chemotactic accuracy and persistence are mutually constrained. Our results suggest that key aspects of chemotactic performance are inherently limited regardless of how favorable the environmental conditions are.