Winona was once an incorporated village called Walnut Creek, until the 1950s when it became part of Flagstaff. Walnut Creek runs through Winona. It has been a dry creek bed since a dam was built above Walnut Canyon in the 1950s to provide Flagstaff with a reservoir. Before this, the creek ran year round.
Winona is located along U.S. Route 66 and was made famous in the song "Route 66". It lies about thirteen miles (19 km) east of Flagstaff and is deliberately out of sequence with the rest of the cities named in the song because of its near-miss: "Don't forget Winona." The author of the song, Bobby Troup, needed a word that rhymed with "Arizona". It is also mentioned in the song "Arizona Yodeler": "Way out in Arizona, in a town they call Winona..."
The singer Wynonna Judd adopted her name upon hearing "Winona" in "Route 66."