We used genetic parentage analysis of 6200 potential parents and 5497 juvenile offspring to evaluate the relative reproductive success of hatchery and natural steelhead (Onchorhynchus mykiss) when spawning in the wild between 2008 and 2011 in the Wenatchee River, Washington. Hatchery fish originating from two prior generation hatchery parents had <20% of the reproductive success of natural origin spawners. In contrast, hatchery females originating from a cross between two natural origin parents of the prior generation had equivalent or better reproductive success than natural origin females. Males originating from such a cross had reproductive success of 26–93% that of natural males. The reproductive success of hatchery females and males from crosses consisting of one natural origin fish and one hatchery origin fish was 24–54% that of natural fish. The strong influence of hatchery broodstock origin on reproductive success confirms similar results from a previous study of a different population of the same species and suggests a genetic basis for the low reproductive success of hatchery steelhead, although environmental factors cannot be entirely ruled out. In addition to broodstock origin, fish size, return time, age, and spawning location were significant predictors of reproductive success. Our results indicate that incorporating natural fish into hatchery broodstock is clearly beneficial for improving subsequent natural spawning success, even in a population that has a decades-long history of hatchery releases, as is the case in the Wenatchee River.