Colonization of vacant habitats is an important process for supporting the long-term persistence of populations and species. We used a before–after experimental design to follow the process of colonization by steelhead Oncorhynchus mykiss (anadromous Rainbow Trout) at six monitoring sites in a natal stream, Beaver Creek, after the modification or removal of numerous stream passage barriers. Juvenile O. mykiss were collected at monitoring sites by using a backpack electrofisher. Passive integrated transponder tags and instream tag reading stations were used in combination with 16 microsatellite markers to determine the source, extent, and success of migrant O. mykiss after implementation of the barrier removal projects. Steelhead migrated into the study area during the first spawning season after passage was established. Hatchery steelhead, although comprising more than 80% of the adult returns to the Methow River basin, constituted a small proportion (23%) of the adult O. mykiss colonizing the study area. Adult steelhead and fluvial Rainbow Trout entered the stream during the first spawning season after barrier removal and were passing the uppermost tag reader (12 km upstream from the mouth) 3–4 years later. Parr that were tagged in Beaver Creek returned as adults, indicating establishment of the anadromous life history in the study area. Population genetic measures at the lower two monitoring sites (lower 4 km of Beaver Creek) significantly changed within one generation (4–5 years). Colonization and expansion of steelhead occurred more slowly than expected due to the low number of adults migrating into the study area.