The streams draining of into San Francisco Bay, California, have been impacted by habitat alteration for over 150 years, and roads, dams, water diversions, and other impediments now block the paths of many aquatic migratory species. These changes can affect the genetic structure of fish populations, as well as driving adaptive evolution to novel environmental conditions. Here, we determine the evolutionary relationships of San Francisco Bay Area steelhead/rainbow trout (Oncorhynchus mykiss) populations and show that (i) they are more closely related to native coastal steelhead than to the California Central Valley lineage, with no evidence of introgression by domesticated hatchery rainbow trout, (ii) populations above and below barriers within watersheds are each other's closest relatives, and (iii) adaptive genomic variation associated with migratory life-history traits in O. mykiss shows substantial evolutionary differences between fish above and below dams. These findings support continued habitat restoration and protection of San Francisco Bay Area O. mykiss populations and demonstrate that ecological conditions in novel habitats above barriers to anadromy influence life-history evolution. We highlight the importance of considering the adaptive landscape in conservation and restoration programs for species living in highly modified habitats, particularly with respect to key life-history traits.