Cottonwood was named for the large number of cottonwood trees in the vicinity. Charles Heinrich founded the town in 1852 when he established a store. The same year he bought 160 acres (65 ha), which were bounded on each side by land purchased by others. This area was served by the Cache Creek Post Office which began its service on March 24, 1852. A racetrack was constructed by Andrew Work about one mile northeast of the store that Heinrich built. The upkeep of animals at the racetrack made way for the establishment of a local blacksmith in 1852.
In 1861 Henry and Caroline Fredrick gave three acres for a Union School on the corner of roads 90 and 23. By 1870 the area had a hotel, a saloon, two stores, a blacksmith, a wagon maker, a saddler, and a shoemaker. A Congregational Church building was also present.
Many of the buildings, businesses, and residents of Cottonwood moved from their little town to Madison, one mile north, when the a rail line connecting Vaca Valley to the Clear Lake Railroad line bypassed them on its way to Madison. The decision to bypass Cottonwood was made when D.B. Hurlbut gave the right-of-way through his land and a $1,000 donation for the rail-company to construct a terminal in Madison. The road was graded from Winters to Hurlbut's land by area resident George W. Scott. Even the Cache Creek Post Office moved to Madison on March 29, 1877. The only thing left in Cottonwood was the Cottonwood Cemetery with tombstones from the 1860s and 1870s. The Cottonwood Cemetery is still in active use today.