The land Neodesha now sits upon was first settled by the Osage Indians in the early 1800's.   Coming from an Osage word, Neodesha means "where waters meet." And the town is appropriately named, sitting between the Verdigris and Fall Rivers.

In October, 1867, A. McCartney and A. K. Phelon came from Neosho Falls to the neighborhood of what is now Neodesha and established a trading post for traffic with the Osage Indians. This post stood near the now famous Little Bear Mound. Nearly a year before this time, while the Indians still held the land, and the whites had no rights in the premises, E. K. Parris and A. Tucker had built a cabin on Fall River some distance west of the future town site, and sold goods to the Indians. Other settlements had been made still earlier, but none near Neodesha. Numerous Indian villages were near the junction of the Verdigris and Fall River, and the Osages had given to the place the name of Neodesha (meeting of the waters), which soon came to be applied to the trading post.

In October, 1868, R. S. Futhey and John B. Keys arrived at the trading post, and after looking over a suitable spot for a town site, selected the claim where the city now stands, paying therefore $500. This was the signal for a wild excitement, and all claims near that of Futhey and Keys being held at enormous figures. McCartney and Phelon joined Futhey and Keys in the formation of a town company and a survey of the town site, which took place on July 12 and 13, 1869. On December 24, of that year, the frame of the first building on the town site was raised, and on its completion McCartney and Phelon moved into it the stock of the trading post. The policy of the town company was most liberal, lots being freely given to all who would erect buildings, and the town went on with a rush which soon carried it beyond the other settlements on the Trust lands. In one year from the erection of the McCartney and Phelon store there were 200 buildings in the town, and six months later the population had reached 1,000.