Established February 23, 1854, this county was named for a Dakota woman, Winona, cousin of the last chief named Wabasha, both of whom were prominent in the events attending the removal in 1848 of the Winnebago Indians from Iowa to Wabasha's Prairie (the site of the city of Winona) and thence to Long Prairie in Todd County. This name belonged, said Prof. A. W. Williamson, in any Dakota family, to the "first born, if a daughter, diminutive of wino, woman"; and similarly the name of the "first born child, if a son," was Chaska. In pronunciation, Winona is accented on the middle syllable, and the first and last syllables have the short vowel sounds. The first, however, is often incorrectly given the long sound, as in wine; it should be short, as in win, or may be quite rightly given the sound of long e, as we.

William H. Keating gave an impressive narration of the death of a Dakota maiden named Winona, who threw herself to death from the precipice known as "the Maiden's Rock," on the east shore of Lake Pepin, in preference to being married, as her parents requested, to one whom she did not love (Narrative of Long's Expedition, 1823, vol. 1, pp. 289-95). With much amplification, including change of the home of the maiden from Wabasha's village of Keoxa to a Dakota village represented to have been near St. Anthony Falls, Hon. Hanford L. Gordon retold this tragedy in a poem bearing her name, "Winona," published in 1881, reprinted in his collected writings (Indian Legends and Other Poems, 1910, pp. 43-74).

This name was first applied, about a year before the establishment of the county, to the village of Winona, which became the county seat.