Covering 12,096 acres, Natchez Trace State Park is located approximately five miles east of Wildersville. In combination with the Natchez Trace State Forest, which includes nearly 36,000 acres in Henderson, Carroll, and Benton Counties, the two sites comprise West Tennessee's largest state-owned recreational area. Initially the site included some of the state's most eroded lands, with gullies measuring up to seventy-five feet deep and three hundred feet wide. Now the Natchez Trace State Park Visitor's Center exhibits historic photographs of these huge gullies, and a small portion of the devastated land has been preserved.
Three New Deal agencies, the Works Progress Administration (WPA), the Civilian Conservation Corps (CCC), and the Resettlement Administration, assumed responsibility for the park's initial planning and development. Like other early state parks, the Resettlement Administration relocated property owners from unproductive and overused farm land; the CCC and WPA began land replenishment and park construction. The CCC concentrated its efforts on reforestation work and instigated land stabilization programs that included the introduction of the Japanese vine kudzu to halt erosion.
In 1939 the U.S. Department of Agriculture leased land to the state for the development of Natchez Trace State Park, and the CCC and WPA began park construction. These two agencies built a lake, public lodge, bathhouse, beach, twenty brick cabins, outdoor fireplaces, picnic areas, a group camp, hiking trails, and a recreational building. Additional building plans included an athletic field, amphitheater, assembly hall, dining hall, kitchen, ten cabins, two washhouses, and two lakes. These plans failed to materialize as state interest in the park, which was used as a resort and a fish and game refuge, declined. Six years later, the site had still not become a popular tourist attraction. The park's remote location, minimal attractions, and poor planning, construction, and development all contributed to the paucity of visitors. State officials viewed the development of the site as too expensive and abandoned all work except the construction of camping facilities. In 1949 a renovation program closed the park for remodeling of cabins and rangers' houses, reconstruction of the swimming area, and renovation of the administrative area.
The Division of State Parks emphasized the historical features of Natchez Trace State Park. The park's name reflects the assumption that the old Natchez Trace passed through the land; later research identified the original route several miles east of the park. Park officials also attempted to raise visitation by associating the area with nearby Indian burial grounds and featuring within the park a large pecan tree that measured 17 feet in circumference and approximately 106 feet in height in 1960.
Park officials now believe that the CCC and WPA completed all 1930s era buildings and structures for the park, but few of these remain intact. A fire tower and water tower constructed in 1937, probably by the CCC, are still visible. The WPA constructed the Colonial Revival-style park lodge. The park's unique depression-era project is Fairfield Gullies, a well-preserved area that demonstrates the former severely eroded lands of West Tennessee and the introduction of kudzu as a conservation method.