Fish migrations are energetically costly, especially when moving between fresh and saltwater, but are a viable strategy for Pacific salmon and trout (Oncorhynchus spp.) due to the advantageous resources available at various life stages. Anadromous steelhead (O. mykiss) migrate vast distances and exhibit variation for migration phenotypes that have a genetic basis at candidate genes known as greb1L and rock1. We examined the distribution of genetic variation at 13 candidate markers spanning greb1L, intergenic, and rock1 regions versus 246 neutral markers for 113 populations (n = 9,471) of steelhead from inland and coastal lineages in the Columbia River. Patterns of population structure with neutral markers reflected genetic similarity by geographic region as demonstrated in previous studies, but candidate markers clustered populations by predominate genetic variation associated with migration timing. Mature alleles for late migration had the highest frequency overall in steelhead populations throughout the Columbia River, with only 9 of 113 populations that had a higher frequency of premature alleles for early migration. While a single haplotype block was evident for the coastal lineage, we identified multiple haplotype blocks for the inland lineage. The inland lineage had one haplotype block that corresponded to candidate markers within the greb1L gene and immediately upstream in the intergenic region, and the second block only contained candidate markers from the intergenic region. Haplotype frequencies had similar patterns of geographic distribution as single markers, but there were distinct differences in frequency between the two haplotype blocks for the inland lineage. Redundancy analyses were used to model environmental effects on allelic frequencies of candidate markers and significant variables were migration distance, temperature, isothermality, and annual precipitation. This study improves our understanding of the spatial distribution of genetic variation underlying migration timing in steelhead as well as associated environmental factors and has direct conservation and management implications.