Evolution experiments have demonstrated high levels of genetic parallelism between populations evolving in identical environments. However, natural populations evolve in complex environments that can vary in many ways, likely sharing some characteristics but not others. Here we ask whether shared selection pressures drive parallel evolution across distinct environments. We addressed this question in experimentally evolved populations founded from a clone of the bacterium Burkholderia cenocepacia. These populations evolved for 90 days (approximately 600 generations) under all combinations of high or low carbon availability and selection for either planktonic or biofilm modes of growth. Populations that evolved in environments with shared selection pressures (either level of carbon availability or mode of growth) were more genetically similar to each other than populations from environments that shared neither characteristic. However, not all shared selection pressures led to parallel evolution. Genetic parallelism between low-carbon biofilm and low-carbon planktonic populations was very low despite shared selection for growth under low-carbon conditions, suggesting that evolution in low-carbon environments may generate stronger tradeoffs between biofilm and planktonic modes of growth. For all environments, a population’s fitness in a particular environment was positively correlated with the genetic similarity between that population and the populations that evolved in that particular environment. Although genetic similarity was low between low-carbon environments, overall, evolution in similar environments led to higher levels of genetic parallelism and that genetic parallelism, in turn, was correlated with fitness in a particular environment.