Odor cues guide animals to food and mates. Different environmental conditions can create differently patterned odor plumes, making navigation more challenging. Prior work has shown that animals turn upwind when they detect odor and cast crosswind when they lose it. Animals with bilateral olfactory sensors can also detect directional odor cues, such as odor gradient and odor motion. It remains unknown how animals use these two directional odor cues to guide crosswind navigation in odor plumes with distinct statistics. Here, we investigate this problem theoretically and experimentally. We show that these directional odor cues provide complementary information for navigation in different plume environments. We numerically analyzed real plumes to show that odor gradient cues are more informative about crosswind directions in relatively smooth odor plumes, while odor motion cues are more informative in turbulent or complex plumes. Neural networks trained to optimize crosswind turning converge to distinctive network structures that are tuned to odor gradient cues in smooth plumes and to odor motion cues in complex plumes. These trained networks improve the performance of artificial agents navigating plume environments that match the training environment. By recording Drosophila fruit flies as they navigated different odor plume environments, we verified that flies show the same correspondence between informative cues and plume types. Fly turning in the crosswind direction is correlated with odor gradients in smooth plumes and with odor motion in complex plumes. Overall, these results demonstrate that these directional odor cues are complementary across environments, and that animals exploit this relationship.