Indianola probably began in 1875, when H. M. McElhany moved to the area and opened a one-room store. The store also served as a mail drop for local residents. The mail was delivered by horseback from the nearby town of Canadian, Oklahoma. McElhany stayed in business for about three years, then sold the store to Albert S. Cornelison and James H. Bynum. An actual post office was established at Indianola, Indian Territory on January 16, 1891, with Bynum being appointed as the first postmaster.