There were a series of small settlements near Waltonville prior to its formation. In 1840, Eli Gilbert dammed Rayse Creek about a mile northeast of Waltonville, near the point where the Mt. Vernon/Pinckneyville road crossed the creek. He built a saw mill, grist mill and store at this location, which was called "Mill Town". In 1860, Knob Creek Post Office was opened there. This was in McClellan Township.
In 1867, a settlement called Williamsburg was started, about a half mile west of Mill Town. This was in Knob Prairie, Blissville Township, just to the north of the present town of Waltonville. Knob Prairie owes its name to a steep hill, or knob, that arises just to the northwest of Waltonville. The town's water tower sits atop the knob.
Williamsburg was platted in 1867. It was possibly named for the surveyor, J. D. Williams. Williamsburg was at the intersection of the Shawneetown/Nashville and Mt. Vernon/Pinckneyville Roads, neither of which exist any more. After the post office refused to recognize the "Williamsburg" name, it was called the "Laur Post Office", after Capt. Joseph Laur, who commanded a local company in the Civil War.
Waltonville, to the south of the knob, started as a small store owned by Rob Mannen. The town was named for his mother, Eliza A. Walton Mannen. The town took off in 1893 with the completion of a rail line from Mt. Vernon to Chester. Williamsburg moved down to the new rail depot. The rail line is now part of the Union Pacific system.
The Universalist Church existed in Williamsburg prior to 1870, and moved to Waltonville before 1906. This church was still operating as late as 1980. Waltonville was for many years the smallest town in the United States to have a Universalist Church. This may be another reflection of the numerous obscure ethnic groups that maintained an identity in the rural coal fields of Southern Illinois.
Many underground coal mines were opened near Waltonville. Immigrants came to work these mines, mainly from Poland. By the 1950s, the rurual areas West of Waltonville were predominantly Polish, and the main language spoken was Polish. That language slowly faded with the advent of television. Today, only a few people speak any Polish. Many still identify as Polish, though, and they continue to attend St. Barbara's Catholic Church in nearby Scheller, IL.
In 2011, the Waltonville Lake was breached, resulting in the complete draining of the lake in order to make the necessary repairs.