Directed cell migration guided by external cues plays a central role in many physiological and pathophysiological processes. The microenvironment of cells often simultaneously contains various cues and the motility response of cells to multiplexed guidance is poorly understood. Here we combine experiments and mathematical models to study the three-dimensional migration of breast cancer cells in the presence of both contact guidance and a chemoattractant gradient. We find that the chemotaxis of cells is complicated by the presence of contact guidance as the microstructure of extracellular matrix (ECM) vary spatially. In the presence of dual guidance, the impact of ECM alignment is determined externally by the coherence of ECM fibers and internally by cell mechanosensing Rho/Rock pathways. When contact guidance is parallel to the chemical gradient, coherent ECM fibers significantly increase the efficiency of chemotaxis. When contact guidance is perpendicular to the chemical gradient, cells exploit the ECM disorder to locate paths for chemotaxis. Our results underscore the importance of fully characterizing the cancer cell microenvironment in order to better understand invasion and metastasis.