In 1894, almost 120 years ago, a federal report was published having the title "Investigations in the Columbia River Basin in Regard to the Salmon Fisheries; The Salmon Fisheries of the Columbia River Basin." The author was Marshall McDonald, the United States commissioner of Fish and Fisheries.
This report contained a map titled "The Natural Limits of Distribution of Salmon in the Columbia River Basin."
It's interesting to see that the area in and around Walla Walla, apparently including Mill Creek and the upper Walla Walla River, was shown on this map made in 1894 to be not included in the natural limits of the distribution of salmon.
Another 1890's-era federal report, titled "A Report Upon Investigations in the Columbia River Basin with Descriptions of Four New Species of Fish," by Charles Gilbert and Barton Evermann, mentions regarding Mill Creek downstream of Walla Walla that "we could not learn that salmon are ever taken in this stream."
On the lower Walla Walla River, this report mentions August water temperatures of 70 degrees, and the water being "rather muddy."
It is an interesting exercise to compare these 1894 descriptions to those noted in 2012.