Keystone, once notorious because of its widely known red-light district called Cinder Bottom, is located beside Elkhorn Creek on the main line of the Norfolk & Western Railway in McDowell County. The town was incorporated in 1909. Serving surrounding coal company towns, Keystone became a regional center for wholesale grocers, retail stores, saloons, and entertainment as the area underwent rapid population growth. It was named for Pennsylvania, the Keystone State, from which many coal officials came.

Keystone was known for its racial diversity. Boasting the state's first-ever African-American mayor, as well as M. T. Whittico's McDowell Times, the state's leading minority newspaper, Keystone was a center of McDowell County's "Free State" community of color. The fictional town of Annadel in Denise Giardina's novel, Storming Heaven, is based on Keystone.

Keystone had 2,500 residents by 1950, when the closing of some local mines and the mechanizing of others began to reduce the population. The saloons and brothels began to close as the population waned, as did the town's respectable businesses. Floods and fires threatened the community. Keystone received widespread attention in 1999 when the First National Bank of Keystone was closed by federal agencies, in one of the costliest bank failures in FDIC history. Several bank managers were tried and convicted on various charges. In 2010, Keystone’s population was 282.