Local historian Alex Finley claimed the area was first settled by Gasper Butcher , but others have questioned this. Although the area is known to have been called Big Boiling Spring, Gasper Butcher's Spring, and Butcher's Station, W.R. Jillson was unable to find written records of habitation before William Cook and his wife erected Cook's Cabin with eighteen-year-old William Stewart in 1790. Also known as Cook's Station, the community located about east of the present city became Logan Court House when it was chosen to be the seat of the newly formed Logan County in 1792. Logan Court House moved west to its present location when it was laid off in 1795 on part of Gen. William Russell's grant for his military service during the American Revolution. The town was renamed in his honor in 1798 and formally established by the state legislature on January 15, 1810. It was incorporated as a city on February 19, 1840.
In the early 19th century, the community was politically prominent and four homes in the city still stand which housed future governors of Kentucky: John Breathitt, James Morehead, John J. Crittenden, and Charles S. Morehead.
During the Civil War, the Kentucky General Assembly declared its neutrality and declined to secede with the rest of the South, despite being a slave state. In 1862, 116 sympathizers of the rebellion from 43 counties met as the Russellville Convention and created a separate Confederate government for Kentucky. George W. Johnson was elected as the state's governor. Despite de facto Union control over Kentucky, this shadow government was recognized and admitted by the Confederacy, the source of the thirteenth star on the Confederate flag.
After the war, Kentucky struggled with insurrections. A gang made up of the former Confederate guerrillas Cole Younger, George Shepard, and Oliver Shepard, along with Confederate veterans John Jarrett and Arthur McCoy, robbed the Nimrod Long Bank or the Southern Deposit Bank in Russellville on March 20, 1868. The brothers Frank and Jesse James, who later led their own gang, may have participated in peripheral roles. Today a Russellville bank on the city square has a large mural depicting the robbery. A reenactment of the robbery (called a "play on horseback") is performed annually during the city's Tobacco and Heritage Festival.
Several downtown homes have been listed on the National Register of Historic Places.