Navasota is on a bend of the Navasota River at the intersection of State Highway 105 and Farm roads 3090 and 1227 in southeastern Grimes County. The site was first named Hollandale for Francis Holland, who bought land in the area in 1822. In 1832 a Georgia planter named Daniel Arnold moved to the vicinity. In 1848 James Nolan set up some tents nearby, and by 1852 he had built a log cabin that became a stage stop. The site was a natural crossroads, as it was located near the spot where the La Bahía Road crossed the Navasota River, and about halfway between Anderson and Washington-on-the-Brazos. By the mid-1850s four stage lines had established stops in the vicinity. The settlement name was changed to Navasota (for the river) in 1854, when a post office was established there. After September 1859, when the Houston and Texas Central Railway built into the town, Navasota became even more important as a shipping and marketing center for the surrounding area. Cotton, gunpowder, and guns were stored there during the Civil War. By 1865 the population was about 2,700.
The town, however, suffered a series of disasters in the mid-1860s that severely depleted its population. In 1865 a warehouse filled with cotton and gunpowder exploded after it was torched by disgruntled Confederate veterans; the blast killed a number of people and started a fire that destroyed or damaged many buildings, including the post office. Not long afterward the town was struck by a deadly cholera epidemic, which was followed in 1867 by an even more dangerous epidemic of yellow fever. As many Navasota citizens, including the mayor, fled to escape the disease, the town population dropped by about 50 percent. During the late 1860s the Ku Klux Klan spread into Navasota, and on one occasion a tense confrontation between federal soldiers and a crowd of local White citizens occurred there.
In October 1866, in the midst of these troubles, Navasota was incorporated; after the yellow fever epidemic its economic fortunes revived. One of the first cottonseed oil mills in the state was built there before 1880. By 1884 about 2,500 people were living in Navasota, and in addition to the oil mill the town had five churches, two flour mills, several steam-powered cotton gins, a bank, an opera house that could seat 1,000, and a newspaper, the Navasota Tablet. A telephone company began operating there in 1885; that same year the town gained another railroad connection when the Gulf, Colorado and Santa Fe built through. In the late 1880s the town contracted for its first water system and electrical lights. By 1896 four weekly newspapers were being published in Navasota, and the town had grown to a population of about 3,500.
The International-Great Northern became the town's third railroad in 1900, and for the next three decades Navasota continued to grow as a shipping and marketing center for cotton, livestock, lumber, and produce. Its population increased from 3,857 in 1900 to 5,128 by 1930; in 1930, 175 businesses were reported in the town. Though the number of businesses in Navasota declined slightly during the Great Depression, by 1940 its population had grown to 6,138. During the 1940s the town declined as the farms surrounding it were mechanized and consolidated, and by 1950 only 4,976 residents remained. Hoping to reverse this trend, in 1952 local businessmen began to organize the Navasota Industrial Foundation. The foundation, which later drew tax dollars for its support, worked with some success to attract new industries to the area. The town population stabilized, and by the mid-1970s Navasota had eighteen manufacturers producing mobile homes, furniture, cheese, steel tubing, and oilfield machinery. The population grew from 4,937 in 1960 to 5,026 by 1970 and to 5,971 by 1980. Residents also organized to revitalize the downtown area, and in 1980 Navasota was one of five Texas cities selected for the National Main Street program sponsored by the National Trust for Historic Preservation. During the mid-1980s the Texas Department of Corrections built the minimum-security Wallace Pack prison just outside of town. Though many in Navasota had opposed the prison, the facility produced hundreds of new jobs. Many businesses suffered during the late 1980s, when the oil industry collapsed; one employer alone laid off more than 650 workers. Though the new jobs brought by the prison helped to offset some of the worst effects of the economic downturn, city officials again became concerned that young people would have to move elsewhere for employment. In 1990 the census counted 6,296 people in Navasota. The population grew to 6,789 in 2000.